Problem J
Joyless Game
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?
Input
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)$.
Output
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 |
Chikapu Bash |
