Petya and Gena play a very interesting game "Put a Knight!" on a chessboard *n* × *n* in size. In this game they take turns to put chess pieces called "knights" on the board so that no two knights could threat each other. A knight located in square (*r*, *c*) can threat squares (*r* - 1, *c* + 2), (*r* - 1, *c* - 2), (*r* + 1, *c* + 2), (*r* + 1, *c* - 2), (*r* - 2, *c* + 1), (*r* - 2, *c* - 1), (*r* + 2, *c* + 1) and (*r* + 2, *c* - 1) (some of the squares may be located outside the chessboard). The player who can't put a new knight during his move loses. Determine which player wins considering that both players play optimally well and Petya starts.

The first line contains integer *T* (1 ≤ *T* ≤ 100) — the number of boards, for which you should determine the winning player. Next *T* lines contain *T* integers *n*_{i} (1 ≤ *n*_{i} ≤ 10000) — the sizes of the chessboards.

提交代码