Playing games is the best way to improve flexibility, critical thinking and strategy.
To become the best Pokenom player, Bash is playing some games with his Pokenom Chikapu.
Bash writes down a string $S$ containing only lowercase English letters. No $2$ consecutive characters in $S$ are equal.
Bash and Chikapu alternatively take turns to play.
In each turn, a player must delete one character in $S$. There are $2$ conditions:
The first and last characters can not be deleted.
After the character is deleted, in the new string, no $2$ consecutive characters are equal.
The player who cannot delete a character loses.
Chikapu plays first.
After playing $10^9 + 7$ games, Chikapu won $0$ games and lost all $10^9 + 7$ times. Chikapu thinks that Bash is cheating, by selecting a string $S$ such that Bash always wins.
Given some string $S$, can you help determine who would win the game, if they both play optimally?
The first line of input contains the integer $T$ — the number of test cases $(1 \le T \le 20)$.
The next $T$ lines each contain exactly one string $S$ $(3 \le |S| \le 10^5)$.
For each test case, print on one line the name of the winner, if they both play optimally. Please note that this problem uses case-sensitive checker.
|Sample Input 1||Sample Output 1|
2 vietnam icpc