WILLITST - Will it ever stop


When Bob was in library in University of Warsaw he saw on one of facades caption :"Will it ever stop?" and below some mysterious code:

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

Help him finding it out !

Input

In first line one number n<=10^14.

Output

Print "TAK" if program will stop, otherwise print "NIE"

Example

Input:
4

Output:
TAK

hide comments
xinnix: 2016-06-17 19:17:27

Was printing TAE instead of TAK... got me 2 WA lol....

suraj: 2016-06-14 19:19:43

can't get O(1) solution,help me

top_gun007: 2016-06-12 07:38:34

collatz conjecture-all u need to know

vineetpratik: 2016-06-11 19:06:13

dont use float or double it gives WA , in some testcases. can't figure out why
sol in O(1)

amankumarjha: 2016-05-21 18:31:17

It is a slight modified form of collatz conjecture, but this problem illustrates that how a slight modification can solve a problem so easily.

chen9069: 2016-01-29 17:42:46

O(1) solution, check if n <= 1 || n & (n-1) == 0

Bijoy Rahman Arif: 2016-01-19 19:10:43

WC: O(log2(n)) : this is the best solution I guess.

prasanna132: 2016-01-10 20:30:21

AC with O(1) time :)

nightwolf_9197: 2015-12-22 21:23:49

same algo in pyth 2.7 got AC but got RE in c++

jasbir_220b2: 2015-12-22 07:57:30

easy one....


Added by:Krzysztof Lewko
Date:2011-11-09
Time limit:0.906s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:AMPPZ 2011