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 ≤ 10¹⁴, 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