DCEPC703 - Totient Game

no tags 

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 = number 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

Input

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 ith integer represents the number of stones in the ith pile.

Output

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.

Constraints

1<=T<=10
1<=N<=10^5
1<= Number of stones in each pile <=10^7

Example

Input:
1
3
1 2 3

Output:
Bahl

hide comments
anonymous: 2023-02-17 23:46:50

Really nice problem!

There are test cases where the number of stones is out of [1..10^7] range. Not sure, but probably there are cases with zero stones.

sajjad_hm: 2018-04-27 13:41:35

Totient(i)*Totient(j)=Totient(i*j) if gcd(i,j)=1

[Lakshman]: 2014-05-28 16:08:22

I think all number can be represented in form of Totient(i)*Totient(j)=Totient(i*j) where i+j = n;


Added by:dce coders
Date:2012-04-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem