SP11474 DCEPC703 - Totient Game

Bahl and Debnath are always looking up for new exciting games on the internet. Yesterday, Bahl stumbled across a new game known as “Totient Game”. He immediately showed that to Debnath. They found it pretty exciting and decided to play it. The game is as follows: 1. The game is played with N piles of stones. 2. 2 players play alternatively and at each turn a player selects a pile and divides it into two unequal sized piles “i” and “j” such that Totient(i)\*Totient(j)=Totient(i\*j) and i+j = no. of stones in that pile. 3. The player who is unable to make a move loses the game. Bahl insists on starting the game first. Can you predict the winner of the game? **Assume that both player plays optimally.** [http://en.wikipedia.org/wiki/Euler%27s\_totient\_function](http://en.wikipedia.org/wiki/Euler%27s_totient_function)

First line gives T, the number of test cases. Each test starts with a line containing “N”, the number of piles. Next line gives N space separated integers. The i $ ^{th} $ integer represents the number of stones in the i $ ^{th} $ pile.

Output T lines each containing the winner of the T games. Output “Bahl” if Bahl wins the game or “Debnath” if Debnath wins the game.