ICPC 2025 · Problem B · Blackboard Game

To help her elementary school students understand the concept of prime factorization, Aisha has invented a game for them to play on the blackboard. The rules of the game are as follows.

The game is played by two players who alternate their moves. Initially, the integers from $1$ to $n$ are written on the blackboard. To start, the first player may choose any even number and circle it. On every subsequent move, the current player must choose a number that is either the circled number multiplied by some prime, or the circled number divided by some prime. That player then erases the circled number and circles the newly chosen number. When a player is unable to make a move, that player loses the game.

To help Aisha’s students, write a program that, given the integer $n$, decides whether it is better to move first or second, and if it is better to move first, figures out a winning first move.

Input

The first line of input contains an integer $t$ ($1 \le t \le 40$), which is the number of test cases. The descriptions of $t$ test cases follow.

Each test case consists of a single line containing an integer $n$ ($2 \le n \le 10^{7}$), which is the largest number written on the blackboard.

Over all test cases, the sum of $n$ is at most $10^{7}$.

Output

For each test case, if the first player has a winning strategy for the given $n$, output the word first, followed by an even integer – any valid first move that can be extended to a winning strategy. If the second player has a winning strategy, output just the word second.

Sample Input 1

1
5

Sample Output 1

second

Explanation of Sample 1: For $n= 5$, the first player loses the game regardless of the first move.

• If the first player starts with $2$, the second player circles $4$, and there are no more valid moves left.

• If the first move is $4$, the second player circles $2$. The first player must then circle $1$, and the second player may pick either of the remaining two numbers ($3$ or $5$) to win.

Sample Input 2

2
12
17

Sample Output 2

first 8
first 6