on Game Theory

plz explain me how to solve this…

BMEENA and BKUL are playing a game. There is a pile of N coins . BMEENA and BKUL make their moves alternately , BMEENA starts first . In first move BMEENA takes s coins such that 0 < s < N , from then on a player takes any number of coins which is a divisior of number of coins taken in previous move. One who makes the last move is winner . Find out who is the winner, assuming they both play optimally?
Input

First line contains the number of testcases T. Then each of next T lines contains an integer N.
Output

For each testcase output a line containing “BMEENA” or “BKUL” ( quotes are for clarity ) accordingly who is the winner.
Constraints

1 <= T <= 10
2 <= N <= 1,000,000
Example

Input:
1
5

Output:
BMEENA

Please add a link to problem statement, it’s interesting. Just an observation, if N % 2 == 1 winner is first player (takes N - 2 coins, second have to take 1 and first gets last coin…)

1 Like

for N % 2 you can find prime p > (N/2) and first is winner again (holds for N >= 8), so there are only 2, 4 and 6 to figure out, you can try brute force here…

//