#U2223DS2. Circular Barn

Circular Barn

[USACO22DEC] Circular Barn S

题目描述

Farmer John 和他的死对头 Farmer Nhoj 在一个环形牛棚内玩游戏。牛棚内有 N(1N105)N(1 \le N \le 10^5) 个房间,第 ii 个房间初始时内有 aia_i 头奶牛 (1ai5×106)(1 \le a_i \le 5 \times 10^6)。游戏玩法如下:

  • 两位农夫将总是在同一个房间里。进入一个房间后,每位农夫各执行一次行动,Farmer John 在先。两位农夫在游戏开始时进入房间 11
  • 如果当前房间中的奶牛数量为零,则此时执行行动的农夫即失败。否则,执行行动的农夫选择一个整数 PP,其中 PP11 或一个不超过当前房间中奶牛的数量的质数,并从当前房间中移除 PP 头奶牛。
  • 两位农夫均完成行动之后,两位农夫移动到环形牛棚的下一间房间。也就是说,如果农夫们在房间 ii,那么他们会移动到房间 i+1i+1,除非他们在房间 NN,在这种情况下他们会移动到房间 11

当两位农夫均采用最优策略时,求获胜的农夫。

输入格式

输入包含 TT 个子测试用例。输入的第一行包含 T(1T1000)T(1 \le T \le 1000)。下面是 TT 个子测试用例。

每个子测试用例的第一行包含 NN,第二行包含 a1,,aNa_1, \cdots ,a_N

输入保证所有 NN 之和不超过 2×1052 \times 10^5

输出格式

对于每一个子测试用例,输出获胜的农夫,为 Farmer JohnFarmer Nhoj 之一。

样例 #1

样例输入 #1

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

样例输出 #1

Farmer Nhoj
Farmer John
Farmer John
Farmer John
Farmer Nhoj

提示

样例 1 解释

对于第一个子测试用例,Farmer John 可以从第一个房间中移除 112233 头奶牛。无论他移除多少头奶牛,Nhoj 都可以移除剩余的奶牛,迫使 FJ 在他们绕回第一个房间时失败。

对于第二个子测试用例,FJ 可以移除 55 头奶牛,迫使 Nhoj 面对剩下的 44 头奶牛。现在,Nhoj 可以移除 112233 奶牛。现在的情况类似于第一个子测试用例。

对于第三个和第四个子测试用例,FJ 可以立即移除第一个房间的所有奶牛,使 Nhoj 失败。

对于第五个子测试用例,FJ 可以从第一个房间中移除 112233 奶牛,然后 Nhoj 可以随后移除余下的奶牛。当他们绕回第一个房间时,FJ 将会失败。

测试点性质

  • 测试点 242-4 满足 N=1N=1
  • 测试点 1,2,571,2,5-7 满足 ai1000a_i \le 1000
  • 测试点 8208-20 没有额外限制。