이 프로그램은 멈출까?

시간 제한3초메모리 제한64 MB

요약

n이 10^14 이하일 때, 짝수면 2로 나누고 홀수면 3n+3으로 바꾸는 루프가 멈추는지 판정한다.

난이도: 보통10점 중 6점
유형: 수학, 정수론, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

Byteasar는 대학교 도서관을 거닐다가 건물 외벽 한쪽에서 "이 프로그램은 멈출까?"라는 문구와 함께 적힌 프로그램 조각을 발견했습니다. 질문이 흥미로워 보여 집으로 돌아온 뒤 직접 풀어 보려 했지만, 코드를 옮겨 적는 과정에서 실수를 해 다음과 같이 적고 말았습니다.

while n > 1 do
  if n mod 2 = 0 then
    n := n / 2
  else
    n := 3 · n + 3

Byteasar는 변수 $n$ 의 어떤 초기값에 대해 자신이 적은 이 프로그램이 멈추는지 알아내려 합니다. 변수 $n$ 의 크기에는 제한이 없어서, 임의로 큰 값을 가질 수 있다고 가정합니다.

입력

첫 번째 줄이자 유일한 줄에 정수 $n$ 이 하나 주어집니다 ( $2 \le n \le 10^{14}$ ).

출력

주어진 $n$ 에 대해 프로그램이 멈추면 TAK(폴란드어로 "예")를, 그렇지 않으면 NIE(폴란드어로 "아니오")를 첫 번째 줄이자 유일한 줄에 출력합니다.

예제3

예제 1
입력
```
4
```
예상 출력
```
TAK
```
예제 2
입력
```
2
```
예상 출력
```
TAK
```
예제 3
입력
```
3
```
예상 출력
```
NIE
```