NKDIV - N..K..Divide


Mona and her brother Alaa are very smart kids, they love math a lot and they are passionate to invent new games.

So after they went back from school they invented a new game called "N..K..Divide".

First of all, let's define a function D(m). such that D(m) is the number of distinct primes in the prime factorization of m. For Example D(9) = 1 and D(12) = 2.

The rules of the game are simple:

  • The game consists of R rounds.
  • In each round there are two integer numbers n and k.
  • Each round consists of multiple turns.
  • Each player alternately takes turn (starting with the player who won the last round / by Mona in the first round).
  • In each turn the player choose some positive integer m, where 2 ≤ m ≤ n such that n is divisible by m and D(m) ≤ k, then divides n by the chosen m.
  • The first player who cannot make any valid move loses.
  • The player who wins more rounds is declared as the winner of the game (if tie then Mona is considered the winner).

So the kids asked their father to run the game for them.

For each of the R rounds father gives them two integer numbers n, k and wants to know who will be the winner of this round if they both play optimally (to win the current round).

Input

The first line consists of a single integer 1 R 10 the number of rounds the kids are going to play.
Each of the next R lines contains two space-separated integers n, k where 2 ≤ n ≤ 1014, 1 ≤ k ≤ 10.

Output

Print R+2 lines.

For the first R lines, the i'th line of them should contain the name of the winner of i'th round if both players play optimally "Mona" or "Alaa" (without quotation marks).

The line number R+1 is an empty line.

In the last line print the name of the winner, print "Mona" if Mona is the winner of the game otherwise print "Alaa" (without quotation marks).

Example

Input:
5
3 4
6 2
6 1
9 1
18 2

Output:
Mona
Mona
Alaa
Alaa
Alaa

Alaa

hide comments
nadstratosfer: 2021-02-09 00:45:21

Beware of blanklines in input when solving with Python.

Sushovan Sen: 2017-10-18 19:04:38

HI Abdullah, Will you please tell me If my solution is wrong or is it failing in certain cases?

abdullahalabd: 2017-09-26 23:18:45

Edited.. Thanks Blue.Mary, their goal is to win each round independently.
P.S: fixed the issue with test data, please resubmit your code now.

Last edit: 2017-09-27 00:33:53
[Rampage] Blue.Mary: 2017-09-26 18:46:23

What does "they both play optimally" mean? What's their goal? To win each round independently, or to win the whole game, or to maximize the number of rounds wins by him/herself?

Edit: according to the sample, the two kids only want to do their best to win each round. So there's a big chance the test data has some issues/errors.

Last edit: 2017-09-26 19:49:27

Added by:Abdullah.Alabd
Date:2017-09-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All