Uolevi and Maija have some fruits. Uolevi has some apples and Maija has some bananas. Also, they have a coconut.

Uolevi and Maija decided to play a game. They put their apples, bananas and the only coconut in a row on a table. Players take turns, Uolevi is the first to make a move.

An apple or a banana is considered tasty if and only if there is no other fruit lying on the table between this apple or banana and the coconut.

On his turn, Uolevi must take a tasty apple from the table and eat it. If there are no tasty apples at the moment, Uolevi skips his turn. Similarly, on her turn, Maija must take a tasty banana from the table and eat it. If there are no tasty bananas at the moment, Maija skips her turn.

The player who eats all his or her fruit before the opponent is declared to be the winner of the game.

Given the initial placement of the fruits on the table, determine who will win the game if both players play perfectly and strive to win.

Input

The first line of the input contains a single integer t, the number of test cases.

Each of the next t lines contains a string consisting of uppercase English letters A, B and C, the initial placement of the fruits in the row, in order from left to right. A stands for an apple, B stands for a banana and C stands for a coconut. There is at least one apple, at least one banana and exactly one coconut in the row.

Output

For each test case output the name of the winner of the game. (Uolevi or Maija)

Constraints

• 1 \le t \le 10^4
• The sum of the lengths of the inputs is at most 10^6

Example

Input:

3
AAACBB
CABAB
BBBBCBA

Output:

Maija
Uolevi
Maija