C. Monocarp, Polycarp and Brackets
time limit per test
3 с
memory limit per test
512 megabytes
input
standard input
output
standard output

A bracket sequence is called regular if it is possible to obtain correct arithmetic expression by inserting characters '+' and '1' into this sequence. For example, sequences (())(), () and (()(())) are regular, while )(, (() and (()))( are not. Let's call a regular bracket sequence an RBS.

Monocarp and Polycarp play a game. They have a string $$$s$$$ consisting of characters of two types: opening brackets and closing brackets. Monocarp also has a string $$$t$$$, which is initially empty.

The players take turns, Monocarp goes first. During Monocarp's turn, he has to choose either the first or the last character of the string $$$s$$$, remove it from $$$s$$$, and append it to the end of the string $$$t$$$. During Polycarp's turn, he has to choose either the first or the last character of the string $$$s$$$ and remove it.

If at any point in time, the string $$$t$$$ becomes a non-empty RBS, Monocarp wins. If the string $$$s$$$ becomes empty, and Monocarp has not won yet, Polycarp wins.

You have to determine which player wins if they play optimally.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains one integer $$$n$$$ ($$$3 \le n \le 6000$$$) — the length of the string $$$s$$$.

The second line of each test case contains $$$s$$$ — a string consisting of $$$n$$$ characters. Each character of $$$s$$$ is either an opening bracket (ASCII code 40), or a closing bracket (ASCII code 41).

Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$6000$$$.

Output

For each test case, print Monocarp if Monocarp wins, or Polycarp if Polycarp wins.

Example
Input
6
4
(())
5
)((()
7
))))))(
6
()()()
6
((()()
6
()((()
Output
Monocarp
Polycarp
Monocarp
Monocarp
Polycarp
Monocarp
Note

In the first example, Monocarp can choose the leftmost character $$$s$$$ and append it to $$$t$$$. No matter what Polycarp does on his turn, the rightmost character of $$$s$$$ will be a closing bracket; so, Monocarp will be able to make $$$t$$$ an RBS by appending it to $$$t$$$ on the second turn.

In the second example, no matter which character Monocarp chooses on the first turn, the string $$$t$$$ will start with a closing bracket. So, it cannot become an RBS.