Nước Đi Cuối Cùng

Hai người chơi luân phiên trên một dãy đống sỏi. Trong một lượt, người chơi chọn đúng một đống còn sỏi và lấy khỏi đống đó một số lượng dương tùy ý. Người không thể thực hiện lượt đi sẽ thua.

Với mỗi ván ban đầu, hãy xác định người chơi thứ nhất hay người chơi thứ hai có chiến lược thắng khi cả hai đều chơi tối ưu.

Input

• Dòng đầu chứa số nguyên $t$, là số ván.
• Mỗi ván gồm hai dòng:
• Dòng thứ nhất chứa số nguyên $n$, là số đống sỏi.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$, trong đó $a_i$ là số sỏi của đống thứ $i$.

Output

• Với mỗi ván, in first nếu người chơi thứ nhất thắng; ngược lại in second.

Constraints

• $1\le t\le 2\cdot 10^5$.
• $1\le n\le 2\cdot 10^5$ cho mỗi ván.
• $1\le a_i\le 10^9$.
• Tổng $n$ của tất cả các ván không vượt quá $2\cdot 10^5$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $t\le 10$, tổng $n\le 20$ và $a_i\le 31$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

3
3
2 5 7
4
1 4 6 8
1
9

second
first
first