맥주 수

어느 날 술집에 모인 전산학자들이 지금까지 마신 맥주잔의 수를 세기로 했다. 맥주를 한 잔 마실 때마다 빈 잔을 탁자에 그대로 쌓아 두니 자리가 부족하고 다음 잔을 나르기도 불편했다. 그래서 그들은 잔을 놓는 두 가지 방향 ⊔ 과 ⊓ 을 각각 이진수의 한 자리로 삼아 수를 기록하기로 했다. 이 방법으로 수를 적는 데 필요한 잔의 수가 크게 줄었다.

그런데 새로운 문제가 생겼다. 시끄럽고 열띤 분위기 탓에, 기록하던 사람은 두 방향 중 어느 쪽을 1 로 정했는지 자주 잊어버렸다. 게다가 수를 왼쪽에서 오른쪽으로 적었는지, 오른쪽에서 왼쪽으로 적었는지조차 헷갈리곤 했다.

하지만 곰곰이 따져 보니, 어떤 수는 이 두 가지 정보(어느 방향이 1 인지, 그리고 읽는 방향)를 몰라도 잔의 배열만으로 원래 수를 유일하게 되살릴 수 있었다. 전산학자들은 이런 수를 맥주 수라고 불렀다. 어떤 수가 맥주 수인지 판별하는 일을 도와주자!

좀 더 정확히 말하면, 양의 정수 $n$ 을 (맨 앞자리가 0 이 되지 않도록) 이진수로 적어 잔으로 표현했을 때, 두 방향 중 어느 것을 1 로 볼지와 읽는 방향을 어떻게 바꾸더라도 같은 잔 배열을 만드는 정수가 오직 $n$ 하나뿐이라면 $n$ 은 맥주 수이다.

첫 번째 줄에 데이터 집합의 개수를 나타내는 작은 정수 $z$ 가 주어진다. 이어서 $z$ 개의 데이터 집합이 차례로 주어진다.

각 데이터 집합은 정수 $n$ 하나로 이루어지며, $1 \le n \le 10^{1000}$ 이다.

각 데이터 집합마다, 주어진 수가 맥주 수이면 TAK 을, 그렇지 않으면 NIE 를 한 줄에 하나씩 출력한다.