Trò chơi Grundy

Hai người chơi thay nhau chia một đống $n$ đồng xu thành hai đống có kích thước khác nhau (đều khác rỗng). Người thực hiện nước đi cuối cùng thắng. Với lối chơi tối ưu, ai sẽ thắng?

Dữ liệu vào

Dòng đầu ghi số lượng truy vấn $t$.

Mỗi dòng tiếp theo ghi một số nguyên $n$ — kích thước đống ban đầu.

Dữ liệu ra

Với mỗi truy vấn, in ra first nếu người đi trước thắng, second nếu người đi sau thắng.

Ràng buộc

• $1\le t\le {10}^5$
• $1\le n\le {10}^6$

Ví dụ