조약돌

조니(Johny)와 마가렛(Margaret)이 "조약돌" 게임을 한다. 탁자 위에 조약돌이 한 줄로 늘어선 $n$개의 더미로 나뉘어 놓여 있다. 이 배치는 다음 성질을 만족한다. 각 더미의 조약돌 개수는 바로 왼쪽 더미의 개수 이상이다(맨 왼쪽 더미는 예외).

두 사람은 번갈아 가며 원하는 더미 하나를 골라 그 더미에서 1개 이상의 조약돌을 가져간다. 단, 가져간 뒤에도 배치가 위 성질(왼쪽에서 오른쪽으로 개수가 줄어들지 않음)을 그대로 만족해야 한다. 즉 어떤 더미도 바로 왼쪽 더미보다 적어질 수 없다. 자기 차례에 더 이상 둘 수 없는 사람(차례가 시작될 때 탁자에 조약돌이 하나도 없는 사람)이 진다. 마가렛의 뛰어난 실력을 감안해 항상 조니가 먼저 시작한다.

마가렛은 매우 강해서 언제나 최선의 수를 두며, 이길 기회가 있으면 반드시 이긴다. 그래서 조니는 주어진 초기 배치에서 자신에게 이길 가능성이 있는지 알고 싶어 한다. 각 질의에 대한 답을 구하는 프로그램을 작성하라.

첫째 줄에 분석할 초기 배치의 개수 $u$ ($1 \le u \le 10$)가 주어진다. 이어지는 $2u$개의 줄에 각 배치가 두 줄씩 주어진다.

각 배치의 첫 줄에는 더미의 개수 $n$ ($1 \le n \le 1000$)이 주어진다. 둘째 줄에는 왼쪽부터 순서대로 각 더미의 조약돌 개수를 나타내는 $n$개의 음이 아닌 정수 $a_i$가 공백 하나로 구분되어 주어지며, $a_1 \le a_2 \le \dots \le a_n$을 만족한다. 한 배치의 조약돌 총합은 10000을 넘지 않는다.

정확히 $u$개의 줄을 출력한다. 양쪽이 모두 최선을 다한다고 할 때, $i$번째 줄에는 $i$번째 배치에서 조니가 이길 수 있으면 TAK을, 반드시 지면 NIE를 출력한다. TAK과 NIE가 출력해야 하는 정확한 문자열이다.