Hide

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
CPU Time limit 1 second
Memory limit 1024 MB
Source The 2018 ICPC Vietnam National Programming Contest
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in