iktk   2년 전

문제

컴퓨터과학자들이 맥주집에서 회식을 하고 있습니다. 그들은 그들이 지금까지 마신 맥주의 양을 빈 맥주잔을 이용해서 표시해 두기로 했습니다.

빈 맥주잔을 전부 테이블 위에 두면 너무 좁기 때문에, 그들은 빈 맥주잔을 바로 두거나(⊔) 뒤집어 두는(⊓) 두 가지 상태로 둘 수 있음을 이용하여 이진 표기법으로 표시해두기로 했습니다.

그런데 문제가 발생했습니다! 그들은 너무 과음을 한 나머지 회식 중간에 갑자기 바로 둔 맥주잔이 1을 나타내는지 뒤집어둔 맥주잔이 1을 나타내는지를 잊어버렸습니다. 심지어, 어느쪽부터 읽어야 하는지도 잊어버렸습니다.

그들은 토론 끝에 이러한 정보가 없어도 지금까지 맥주를 몇 잔 마셨는지 알 수 있는 경우가 있음을 알아냈습니다. 지금까지 마신 맥주가 $n$잔일 때 이 두 정보 없이도 $n$을 알아낼 수 있는 경우, $n$을 "맥주 수"라고 부르기로 했습니다.

양의 정수가 주어졌을 때 이 수가 "맥주 수"인지 판단해봅시다.

입력

입력의 첫 번째 줄에는 데이터 수를 나타내는 작은 정수 $z$이 주어집니다.

다음 줄부터 $z$개의 줄 각각에 테스트케이스가 주어집니다.

테스트케이스는 하나의 정수 $n$($1\le n\le 10^{1000})$로 구성됩니다.

출력

각 테스트케이스에 대해 주어진 $n$이 문제에서 설명한 "맥주 수"이면 "TAK", 그렇지 않으면 "NIE"를 출력합니다.

예제 해석

1 : 빈 맥주잔이 1개이므로, 혼동의 여지가 없습니다.

4 : ⊔가 1, ⊓이 0이라고 정하고 ⊔⊓⊓ 으로 둔 경우, ⊔가 0, ⊓이 1로 정했을 때의 6 (⊓⊓⊔)과 구분할 수 없습니다.

7 : ⊔⊔⊔ 또는 ⊓⊓⊓ 이므로 혼동의 여지가 없습니다.

댓글을 작성하려면 로그인해야 합니다.