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 spaceseparated integers n, k where 2 ≤ n ≤ 10^{14}, 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 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
Sushovan Sen:
20171018 19:04:38
HI Abdullah, Will you please tell me If my solution is wrong or is it failing in certain cases? 

abdullahalabd:
20170926 23:18:45
Edited.. Thanks Blue.Mary, their goal is to win each round independently.


[Rampage] Blue.Mary:
20170926 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?

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