Hide

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

Please log in to submit a solution to this problem

Log in