John
Time limit1sMemory limit128 MB
Determine the winner of a Nim-like misère game where players remove same-colored candies from piles and taking the last candy loses.
- Level
Medium4 of 10
- Topics
- Game theory, Bit manipulation, Math
- Solved
- No attempts yet
Problem
Little John is playing a very funny game with his younger brother. There is one big box filled with colored candies. First John must eat several candies of the same color. Then his opponent takes a turn, and so on, alternating. Note that on each turn a player must eat at least one candy, and all candies eaten in a single turn must be of the same color. Whoever eats the last candy from the box is the loser and has to buy a new candy box.
Both players use an optimal strategy, and John always goes first. Given information about the candies, determine the winner of the game.
Input
The first line contains a single integer -- the number of test cases. Then tests follow, each described by two lines. The first line of each test contains an integer -- the number of different candy colors in the box. The next line contains integers , separated by spaces, where is the number of candies of the -th color.
Output
For each test case, output the winner on its own line. Print John if John wins the game, or Brother otherwise.