Mariusz and Pawel are playing a Prismata game. After many turns the situation is as follows. Pawel has:

• one Gauss Fabricator, with f_h health, which will produce one Gauss Cannon per turn for the next f_l turns
• g Gauss Cannons, each Gauss Cannon has g_h health

Mariusz has t Tarsiers. Each Tarsier has one health. The Gauss Cannon and the Tarsier are the units with one attack. This means that the unit inflicts one damage per turn on a one of the opponent's units. A unit that has lost all its health is immediately destroyed. A unit which has only lost part of its health remains fully operational.

A single turn in Prismata goes like below:

• Mariusz attacks. Mariusz decides how many Tarsiers attack the Gauss Fabricator and how many attack the Gauss Cannons. The same Gauss Cannon can be attacked by more than one Tarsier.
• Pawel attacks. If Pawel has n Gauss Cannons, then Pawel destroys n Mariusz's Tarsiers (Pawel does not make any decisions).
• If the Gauss Fabricator has not yet been destroyed, then it produces one Gauss Cannon with g_h health. Independently of the remaining health, the Gauss Fabricator is destroyed after producing f_l Gauss Cannons. Pawel can start attacking with the new Gauss Cannon in the next turn.

The player who destroys all the opponent's units wins.
Your task is to help Mariusz to find out whether he can win the game and calculate the minimum number of turns needed for the victory.

Input

The first line contains the number of tests T (1 ≤ T ≤ 10). Each of the T next lines contains one test. A single test consists of:

• f_h (1 ≤ f_h ≤ 1000000) - the health of the Gauss Fabricator
• f_l (1 ≤ f_l ≤ 1000000) - the maximum number of Gauss Cannons produced by the Gauss Fabricator
• g_h (1 ≤ g_h ≤ 1000) - the health of a single Gauss Cannon
• g (0 ≤ g ≤ 1000000) - the initial number of Gauss Cannons
• t (1 ≤ t ≤1000000) - the initial number of Tarsiers

Output

For each test your program should output:

• "PAWEL" if Mariusz is unable to win the game
• "MARIUSZ t" if Mariusz can win the game and t is the minimum number of turns needed for the victory

Example

Input:
3
5 100 2 5 7
100 3 10 0 8
100 1 60 0 10

Output:
MARIUSZ 4
MARIUSZ 6
PAWEL

Explanation of the sample tests

Test 1: If left alone, the Gauss Fabricator will produce too many cannons. Therefore Mariusz has to destroy it. One of the possible way for Mariusz to win is:

Turn #1: Mariusz: 7 Tarsiers, Pawel: 5 Gauss Cannons (each with 2 health), the Gauss Fabricator has 5 health

• Mariusz destroys 3 cannons and inflicts one damage on one of the remaining cannons.
• Pawel has 2 cannons. He destroys 2 Tarsiers.
• The Gauss Fabricator produces one cannon.

Turn #2: Mariusz: 5 Tarsiers, Pawel: 3 Gauss Cannons (2 Gauss Cannons with 2 health, one Gauss Cannon with 1 health), the Gauss Fabricator has 5 health

• Mariusz destroys all 3 cannons.
• Pawel hasn't got any cannons, all Tarsiers remain.
• The Gauss Fabricator produces one cannon.

Turn #3: Mariusz: 5 Tarsiers, Pawel: 1 Gauss Cannon with 2 health, the Gauss Fabricator has 5 health

• Mariusz destroys one cannon and inflicts 3 damage on the Gauss Fabricator.
• Pawel hasn't got any cannons, all Tarsiers remain.
• The Gauss Fabricator produces one cannon.

Turn #4: Mariusz: 5 Tarsiers, Pawel: 1 Gauss Cannon with 2 health, the Gauss Fabricator has 2 health

• Mariusz destroys one cannon and the Gauss Fabricator.

Test 2: In this test the Gauss Fabricator has a lot of health but will produce only few cannons. Mariusz should attack only the cannons and wait for the Gauss Fabricator to be destroyed after 3 turns.

Test 3: Even though the Gauss Fabricator will produce only one cannon, the health of this cannon is too high for Mariusz to win.