Giải bài trực tuyến

English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vningame

Johny 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. Johny là người đi trước, biết Margaret luôn chơi tối ưu hỏi Johny có thể thắng được không.

Input

• Dòng đầu tiên là số lượng test u (0 < u < 11).
• 2u dòng tiếp theo mỗi cặp dòng gồm dòng đầu là số lượng đống sỏi N (0 < N < 1001), dòng hai là số lượng các viên sỏi trong các đống sỏi a1 <= a2 <= ... <= an (ai <= 10000).

Output

Nếu Johny thắng in ra TAK nếu không in ra NIE.

Example

 
Input 
2
2
2 2
3
1 2 4
Output 
NIE
TAK