Under construction

Still being built. Things may change

John

Time limit1sMemory limit128 MB

Summary
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 TT -- the number of test cases. Then TT tests follow, each described by two lines. The first line of each test contains an integer NN -- the number of different candy colors in the box. The next line contains NN integers AiA_i, separated by spaces, where AiA_i is the number of candies of the ii-th color.

  • 1≤T≤4741 \le T \le 474
  • 1≤N≤471 \le N \le 47
  • 1≤Ai≤47471 \le A_i \le 4747

Output

For each test case, output the winner on its own line. Print John if John wins the game, or Brother otherwise.

Examples1

  1. Example 1

    Input
    2
    3
    3 5 1
    1
    1
    
    Expected output
    John
    Brother