P14281 [ICPC 2025 WF] Blackboard Game

为了帮助小学学生理解素因数分解的概念，Aisha 发明了一个可以在黑板上玩的游戏。游戏规则如下。 该游戏有两名玩家轮流进行操作。初始时，黑板上写有从 $1$ 到 $n$ 的整数。首先，第一位玩家可以任选一个偶数并将其圈出。之后每一步，当前玩家必须选择一个数字，该数字要么是当前被圈出的数字乘以某个素数，要么是当前被圈出的数字除以某个素数。此后，玩家擦掉原先被圈出的数字，并圈出新选的数字。当某位玩家无法进行操作时，该玩家输掉游戏。 为了帮助 Aisha 的学生，请你编写一个程序，对于给定的整数 $n$，判断是先手好，还是后手好。如果先手有必胜策略，还要输出一个可以实现必胜策略的有效首步。

第一行输入一个整数 $t$（$1\leq t\leq 40$），表示测试用例数量。接下来 $t$ 行，每行一个整数 $n$（$2\leq n\leq 10^7$），表示黑板上的最大数字。 所有测试用例中，$n$ 的总和不超过 $10^7$。

对每个测试用例，如果先手有必胜策略，输出单词 $\text{first}$，并输出一个偶数——表示一个可以实现必胜策略的有效首步。如果后手有必胜策略，仅输出单词 $\text{second}$。

样例 1 解释：对于 $n = 5$，无论先手如何选择，都会输掉这局游戏。 - 如果先手选择 $2$，后手圈出 $4$，无法再进行有效操作。 - 如果首步选择 $4$，后手圈出 $2$，先手只能圈出 $1$，后手可以在剩下的两个数字（$3$ 或 $5$）任意选择获得胜利。 由 ChatGPT 5 翻译