I I U P C   2 0 1 4

Problem C: Happy Birthday Tutu

 

Tutu is a jolly little kitten who is the biggest fan of stone games. His elder brother Milo designed a game for him on the occasion of his 2nd birthday. But Tutu needs another player to play with him, otherwise he will get sad, even on his birthday! L You, being a good old fella, can’t let that happen. So you decided to play with Tutu. But none of you want to lose, so you both play optimally, but as it is his birthday, you let Tutu make the first move.

 

The game consists of K piles, each pile has Ai (1≤i≤K) stones. In each turn, a player can select any number of piles but not all piles (i.e. at most K-1 arbitrary piles) and take any number of stones from all of the selected piles (you can take stones from multiple piles in single move). Note that, the player cannot make an empty move, i.e. at least one stone must be taken in each move. The player, who cannot make a move, loses the game.

 

Given the number of piles and the number of stones in each of the piles, can you determine who wins the game, given that both of you play optimally?

 

Input

First line of input file contains number of test cases, T ≤ 50 and T cases follow. Each case starts with an integer K (1≤ K≤ 100000), number of piles. Next line contains K integers, A1, A2, … AK   ( 0≤Ai≤ 100 ).

 

Output

Output consists of T lines, one for each case. For each case, if Tutu wins, output “Happy Birthday Tutu!”, otherwise print “Better luck next time!” (Quotes for clarity).

 

 

Sample Input

Output for Sample Input

3

1

5

6

1 2 3 4 5 6

4

0 0 0 0

Better luck next time!

Happy Birthday Tutu!

Better luck next time!

 

Problem Setter: Sadia Nahreen