Description

Farmer John and his archrival Farmer Nhoj play a game in a circular barn. The barn has $N$ rooms $(1 \le N \le 10^5)$, and the $i$-th room initially contains $a_i$ cows $(1 \le a_i \le 5 \times 10^6)$. The game proceeds as follows:

• The two farmers are always in the same room. Upon entering a room, each farmer takes one move, with Farmer John moving first. At the start of the game, they enter room $1$.
• If the current room has zero cows, then the farmer whose turn it is loses. Otherwise, the farmer whose turn it is chooses an integer $P$, where $P$ is $1$ or a prime number not exceeding the number of cows in the current room, and removes $P$ cows from the current room.
• After both farmers have completed their moves, they move to the next room in the circular barn. That is, if they are in room $i$, they move to room $i+1$, unless they are in room $N$, in which case they move to room $1$.

Determine the winner when both farmers play optimally.

Input Format

The input contains $T$ subtest cases. The first line contains $T$ $(1 \le T \le 1000)$. Then follow $T$ subtest cases.

For each subtest case, the first line contains $N$, and the second line contains $a_1, \cdots, a_N$.

It is guaranteed that the sum of all $N$ does not exceed $2 \times 10^5$.

Output Format

For each subtest case, output the winner, either Farmer John or Farmer Nhoj.

5
1
4
1
9
2
2 3
2
7 10
3
4 9 4

Farmer Nhoj
Farmer John
Farmer John
Farmer John
Farmer Nhoj

Hint

Sample 1 Explanation

For the first subtest case, Farmer John can remove $1$, $2$, or $3$ cows from the first room. No matter how many he removes, Nhoj can remove the remaining cows, forcing FJ to lose when they loop back to the first room.

For the second subtest case, FJ can remove $5$ cows, forcing Nhoj to face the remaining $4$ cows. Now Nhoj can remove $1$, $2$, or $3$ cows. The situation is now similar to the first subtest case.

For the third and fourth subtest cases, FJ can immediately remove all cows from the first room, causing Nhoj to lose.

For the fifth subtest case, FJ can remove $1$, $2$, or $3$ cows from the first room, and then Nhoj can remove the remaining cows afterward. When they loop back to the first room, FJ will lose.

Test Point Properties

• Test points $2$–$4$ satisfy $N=1$.
• Test points $1,2,5$–$7$ satisfy $a_i \le 1000$.
• Test points $8$–$20$ have no additional constraints.

Translated by ChatGPT 5