D. Digits Duel
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

GabMei and TFG are two legends of MaratonaCIn, both World Finalists and now coaches of the next generation. Somewhere along the way, they picked up the nicknames "mastermei" and "the greatest" — nobody remembers who coined them, but the names stuck.

To settle who truly deserves the grander title, they devised a game. At the start of a match, there are $$$N$$$ numbers on the table, corresponding to the values $$$2, 3, 4, \ldots, N+1$$$. Players take turns, and on each turn, the current player must choose a non-empty subset of the remaining numbers and remove it. A removal is only valid if the GCD of all chosen numbers is strictly greater than 1. If a player cannot make a valid move, they lose.

Whenever a subset of $$$X$$$ numbers is removed, the remaining numbers are relabeled to be the smallest consecutive values starting from 2. That is, if there were $$$Y$$$ numbers before the move, the numbers after the removal become $$$2, 3, 4, \ldots, Y+1-X$$$.

Mastermei always goes first. Assuming both players play optimally, determine who wins.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 100$$$), the number of test cases.

Each test case consists of a single line containing one integer $$$N$$$ ($$$1 \le N \le 5 \cdot 10^5$$$).

Output

For each test case, print a single line containing "mastermei" (without quotes) if the first player wins, or "the greatest" (without quotes) otherwise.

Examples
Input
6
1
2
3
4
5
6
Output
mastermei
the greatest
mastermei
mastermei
mastermei
the greatest
Input
6
13
62
1000
123456
131070
262142
Output
mastermei
the greatest
mastermei
mastermei
the greatest
the greatest