{"problem":{"name":"[USACO22DEC] Circular Barn S","description":{"content":"Farmer John 和他的死对头 Farmer Nhoj 在一个环形牛棚内玩游戏。牛棚内有 $N(1 \\le N \\le 10^5)$ 个房间，第 $i$ 个房间初始时内有 $a_i$ 头奶牛 $(1 \\le a_i \\le 5 \\times 10^6)$。游戏玩法如下： - 两位农夫将总是在同一个房间里。进入一个房间后，每位农夫各执行一次行动，Farmer John 在先。两位农夫在游戏开","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8901"},"statements":[{"statement_type":"Markdown","content":"Farmer John 和他的死对头 Farmer Nhoj 在一个环形牛棚内玩游戏。牛棚内有 $N(1 \\le N \\le 10^5)$ 个房间，第 $i$ 个房间初始时内有 $a_i$ 头奶牛 $(1 \\le a_i \\le 5 \\times 10^6)$。游戏玩法如下：\n\n- 两位农夫将总是在同一个房间里。进入一个房间后，每位农夫各执行一次行动，Farmer John 在先。两位农夫在游戏开始时进入房间 $1$。\n- 如果当前房间中的奶牛数量为零，则此时执行行动的农夫即失败。否则，执行行动的农夫选择一个整数 $P$，其中 $P$ 为 $1$ 或一个不超过当前房间中奶牛的数量的质数，并从当前房间中移除 $P$ 头奶牛。\n- 两位农夫均完成行动之后，两位农夫移动到环形牛棚的下一间房间。也就是说，如果农夫们在房间 $i$，那么他们会移动到房间 $i+1$，除非他们在房间 $N$，在这种情况下他们会移动到房间 $1$。\n\n当两位农夫均采用最优策略时，求获胜的农夫。 \n\n## Input\n\n输入包含 $T$ 个子测试用例。输入的第一行包含 $T(1 \\le T \\le 1000)$。下面是 $T$ 个子测试用例。\n\n每个子测试用例的第一行包含 $N$，第二行包含 $a_1, \\cdots ,a_N$。\n\n输入保证所有 $N$ 之和不超过 $2 \\times 10^5$。 \n\n## Output\n\n 对于每一个子测试用例，输出获胜的农夫，为 `Farmer John` 或 `Farmer Nhoj` 之一。\n\n[samples]\n\n## Note\n\n### 样例 1 解释\n\n对于第一个子测试用例，Farmer John 可以从第一个房间中移除 $1$、$2$ 或 $3$ 头奶牛。无论他移除多少头奶牛，Nhoj 都可以移除剩余的奶牛，迫使 FJ 在他们绕回第一个房间时失败。\n\n对于第二个子测试用例，FJ 可以移除 $5$ 头奶牛，迫使 Nhoj 面对剩下的 $4$ 头奶牛。现在，Nhoj 可以移除 $1$、$2$ 或 $3$ 奶牛。现在的情况类似于第一个子测试用例。\n\n对于第三个和第四个子测试用例，FJ 可以立即移除第一个房间的所有奶牛，使 Nhoj 失败。\n\n对于第五个子测试用例，FJ 可以从第一个房间中移除 $1$\n、$2$ 或 $3$ 奶牛，然后 Nhoj 可以随后移除余下的奶牛。当他们绕回第一个房间时，FJ 将会失败。 \n\n### 测试点性质\n\n- 测试点 $2-4$ 满足 $N=1$。\n- 测试点 $1,2,5-7$ 满足 $a_i \\le 1000$。\n- 测试点 $8-20$ 没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8901","tags":["博弈论","USACO","2022","素数判断,质数,筛法"],"sample_group":[["5\n1\n4\n1\n9\n2\n2 3\n2\n7 10\n3\n4 9 4","Farmer Nhoj\nFarmer John\nFarmer John\nFarmer John\nFarmer Nhoj"]],"created_at":"2026-03-03 11:09:25"}}