Problem Description

You are given a 01 sequence $a_{1\sim n}$ of length $n$, and the sequence contains an even number of 1. NIT and TIN take turns performing the following operation, with NIT going first:

• Choose a position $i\ (1\le i\le n)$ such that the interval $[1,i]$ contains an odd number of 1. Then choose a position $j\ (i<j\le n)$. Flip both $a_i$ and $a_j$ (that is, 0 becomes 1, and 1 becomes 0).

When all elements in the whole sequence become 0, the player whose turn it is cannot make a move and thus loses. Assume both NIT and TIN are extremely smart; who will win? It can be proven that the game will always end.

$n$ can be very large, but the number of 1 in the sequence does not exceed $2\times 10^5$.

Input Format

This problem has multiple test cases.

The first line of input contains the number of test cases $T$.

Then follows the description of each test case. The first line of each test case contains two positive integers $n,m$, where $m$ is the number of 1 in the sequence, and it is guaranteed that $m$ is even.

The next line contains $m$ strictly increasing positive integers describing the indices of these 1. Indices start from $1$.

Output Format

For each test case, output one line with a string NIT or TIN, indicating the winner’s name.

3
4 2
1 3
4 4
1 2 3 4
10 4
1 3 7 8

NIT
TIN
NIT

Hint

Explanation of the samples

In the first test case, NIT can choose $i=1,j=3$ to turn all positions into 0, making TIN unable to move.

In the second test case, no matter how NIT plays first, there will be exactly two positions with 1 left. TIN only needs to choose these two remaining positions to turn all positions into 0.

In the third test case, one possible game process is as follows (note that in this process, each move is not necessarily optimal):

• NIT chooses $i=2,j=3$ and flips these two positions. Now the positions of 1 are $1,2,7,8$.
• TIN chooses $i=7,j=9$ and flips these two positions. Now the positions of 1 are $1,2,8,9$.
• NIT chooses $i=1,j=5$ and flips these two positions. Now the positions of 1 are $2,5,8,9$.
• TIN chooses $i=3,j=4$ and flips these two positions. Now the positions of 1 are $2,3,4,5,8,9$.
• NIT chooses $i=4,j=5$ and flips these two positions. Now the positions of 1 are $2,3,8,9$.
• TIN chooses $i=2,j=9$ and flips these two positions. Now the positions of 1 are $3,8$.
• NIT chooses $i=3,j=8$ and flips these two positions. Now there is no 1 in the sequence.
• TIN cannot move, and NIT wins.

Constraints

For all testdata, $1\le T\le 10^4$, $1\le n\le 10^{18}$, $2\le m\le 2\times 10^5$, $\sum m\le 10^6$. It is guaranteed that $m$ is even, and the indices that are 1 are given in increasing order.

• Subtask 1 ($1$ point): $T\le 10^3$, $n\le 10$.
• Subtask 2 ($9$ points): The sequence is all 1.
• Subtask 3 ($40$ points): $T\le 100$, $n\le 100$.
• Subtask 4 ($10$ points): $\sum n\le 10^6$.
• Subtask 5 ($40$ points): No additional constraints.

Translated by ChatGPT 5