Johnny và Margaret đang chơi trò chơi với các viên đá. Ban đầu có ~N~ đống sỏi ở trên bàn thỏa mãn tính chất đống sau có số viên sỏi không ít hơn đống trước.

Hai người chơi lần lượt thực hiện nước đi của mình, mỗi lần chơi họ có thể lấy số viên sỏi tùy ý miễn là phải thỏa mãn điều kiện không giảm như trên.

Khi số sỏi hết mà đến lượt người nào thì người đó thua. Johnny là người đi trước. Biết Margaret luôn chơi tối ưu, hỏi Johnny có thể thắng được không ?

Input

• Dòng đầu tiên là số nguyên dương ~t \leq 10~ là số test.

• Tiếp theo là ~t~ test, mỗi test có ~2~ dòng, trong mỗi test:

  • Dòng đầu là số nguyên dương ~N \leq 1000~, số đống sỏi.
  • Dòng thứ hai là ~N~ số nguyên dương ~a_1 \leq a_2 \leq \ldots \leq a_N \leq 10000~, số sỏi trong mỗi đống.

Output

Nếu Johny thắng in ra "TAK" ("YES" trong tiếng Ba Lan) nếu không in ra NIE ("NO" trong tiếng Ba Lan).

Sample Input

2

2
2 2

3
1 2 4

Sample Output

NIE
TAK