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 ≤ 1014.

Output

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

Example

Input:
4

Output:
TAK

hide comments
sumit suthar: 2015-11-03 10:12:15

nice one :)

garmel: 2015-10-29 11:47:11

hhh....I was unsure while submitting the solution: I was thinking that there is something hiding i didn't take care of....But I got the AC... this is the thing you must think ok: 3(n+1)=2^x which hasn't any solutions

munjal: 2015-10-19 21:16:45

I solved the problem but still unable to figure out what is wrong with http://ideone.com/455XS2
code !!!!!

abhigupta4: 2015-10-09 09:56:26

Changing the type of input to long long int did the trick !

sneh sajal: 2015-08-31 20:34:04

as i/p is large..search for direct formulas :)

skrishna99: 2015-08-29 13:53:04

I spent 4-5 hrs , the key is finding the number is 2^ or not .I used Java long .

Amanpreet Singh: 2015-08-28 04:48:00

4 wrong answer due to silly mistake ... i was printing TAk instead of TAK...very easy ques.

Suvrat Krishna Mishra: 2015-08-25 19:43:43

finally...use bitwise!!!

poojan : 2015-08-19 18:13:10

hardest problem on spoj! it took 1 month to solve! lolz...

ani_991: 2015-06-23 17:23:26

wow.. that was easy :p AC in first attemp


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