The festival of Gensokyo is near! Marisa and Reimu are in charge of the mushroom dishes for the feast (There are plenty of mushrooms in the Forest of Magic). The festival last $t$ days, and each day, Marisa will gather $n$ walloping baskets of mushrooms. However, while she loves grilled mushrooms, Shiitake hotpot is Reimu's gourmet! So instead of fighting as usual, they came up with a game to settle down the dish for each day, with the following rules:
- Each turn, the player takes away an arbitrarily large pile of mushrooms (greater than $0$) from any basket.
- The first person unable to do this loses the game.
Both want to have their comfort dish on the menu, so they will play optimally. Since Marisa was the gatherer however, she'll be the first player. Help Marisa to find the winner of each day!
### Input
- The first line consists of an integer $t$ - the duration of the festival in days.
- The next $t$ groups of lines come under the form of:
- The first line consists of an integer $n$ - the number of baskets.
- The next line contains $n$ integers $A_i$..., representing the number of mushrooms in each baskets.
### Output
Print $t$ lines, each line is "Marisa" or "Reimu" (without quotes) - the winner of each day.
### Constraints
- $1 \le t \le 1000$.
- $1 \le n \le 10^5$.
- $1 \le A_i \le 10^{10}$.
It is guaranteed that the total number of baskets Marisa can gather across all days does not exceed $10^6$.
### Example
Input:
```
3
3
1 2 3
2
2 1
4
1 3 5 7
```
Output:
```
REIMU
MARISA
REIMU
```
