Description

Masha and Stas are playing a game. At the start of the game, a number $n$ is given, along with two positive integers $a, b$, which initially satisfy $a^b \le n$.

Masha moves first. On each turn, a player must increase exactly one of $a$ or $b$ by $1$, but may not make $a^b > n$; otherwise that player loses.

Now Masha wants to know, if both players play optimally, for the same $n$ and different $a, b$, who will win.

Input Format

The first line contains a number $n$.

The second line contains a number $t$, the number of test cases.

The next $t$ lines each contain two numbers $a, b$, describing each test case.

Output Format

Output $t$ lines, one for each test case:

• If Masha wins, output Masha.
• If Stas wins, output Stas.
• If it is a draw, output Missing.

9 
2 
2  2 
1  4 

Masha 
Missing

Hint

Constraints

• For 30% of the testdata, $1 \le n \le 2 \times 10^3$.
• For 100% of the testdata, $1 \le n \le 10^8$, $1 \le t \le 100$, $1 \le a, b, a^b \le n$.

Translated by ChatGPT 5