A. Agorabusiness
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Rodingo "Cria", the god of Creation, has invited the demigods Renang and Wan to spend their break on Mount Olympus. The two of them love fruits, so they will visit the $$$t$$$ markets of this Greek region, known for their high-quality kakis, plantains and other delicacies.

When Renang and Wan enter a market, they visit each of the $$$n$$$ selling points inside this market and buy exactly one packet of fruits from each selling point. All sellers in the market sell their fruits in packets with different numbers of fruits which are sorted in increasing order on their tables.

After leaving the market, to satisfy a whim from Rodingo, Renang and Wan want to open their packets and distribute all their fruits between them in such a way that they are left with the same number of fruits each after the distribution.

However, none of our character is very good with calculations. Therefore, you must help them decide whether or not, for each visited market, they can or cannot accomplish Rodingo's whim.

Input

The first line of input is an integer $$$t$$$ ($$$1 \leq t \leq 100$$$), the number of markets on Mount Olympus. The markets are then described.

The first line of each market's description is an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), the number of selling points in the market. The selling points are then described.

The first line of each selling point's description is the number $$$m$$$ ($$$1 \leq m \leq 10^5$$$) of packets available there. The second line of each selling point's description contains $$$m$$$ distinct positive integers $$$a_1 \lt a_2 \lt \dots \lt a_m$$$ ($$$1 \leq a_j \leq 10^9$$$, for $$$j = 1,2,\dots, m$$$), separated by spaces, where $$$a_i$$$ is the number of fruits inside the $$$i$$$-th packet over this selling point's table.

It is guaranteed that the sum of the number of packets in all markets is at most $$$10^5$$$.

Output

For each market, output in a single line "SIM" (without quotes) if Renang and Wan can buy and distribute the fruits to accomplish their task or "NAO" (without quotes) if they cannot.

Example
Input
2
2
1
1
2
2 4
1
3
2 5 8
Output
NAO
SIM
Note

There are $$$2$$$ markets.

In the first market, there are $$$2$$$ selling points: the first one sells $$$1$$$ packet with $$$1$$$ fruit and the second one sells $$$2$$$ packets with $$$2$$$ and $$$4$$$ fruits, respectively. It can be proven that, no matter how Renang and Wan buy the two packets their task is impossible.

In the second market, there is only $$$1$$$ selling point, selling packages with $$$2$$$, $$$5$$$ and $$$8$$$ fruits, respectively. Renang and Wan may satisfy Rodingo's whim (for example by buing the packet with $$$8$$$ fruits and each of them will be left with $$$4$$$ fruits after the distribution).