F. Jenga
time limit per test
2 с
memory limit per test
512 megabytes
input
standard input
output
standard output

Jenga is a game played by two or more players. They start with a tower of $$$n$$$ rows, each row consists of $$$3$$$ rectangular blocks. Then they remove blocks one by one until the tower falls. The player which breaks the tower loses. Removed blocks are usually placed on top of the tower forming the new row; however, in this problem, we'll consider a modified version of the game: removed blocks are put aside and are never returned to the tower.

Monocarp and Polycarp play Jenga a lot. They noticed that a tower row remains stable if it contains either the two side blocks, or the central block. Of course, if there are any additional blocks in the row, it is also stable. Thus, rows xxx, x.x, xx., .xx, .x. are stable, while rows x.., ..x and ... are unstable. Here and further on, the character 'x' depicts a block which is not removed yet, and '.' represents an empty space after removing a block. If at least one row (even the topmost one) in the tower becomes unstable, the tower immediately falls.

Currently, Monocarp and Polycarp have a tower of $$$n$$$ rows, where some blocks may already be removed (but each row is stable). It is Monocarp's turn now. Given the state of the tower (which blocks are removed and which are still present), you have to determine who wins, assuming both players play optimally.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — the number of test cases.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^4$$$) — the number of rows in the tower.

Then, $$$n$$$ lines follow, the $$$i$$$-th of them contains $$$6$$$ characters in the format ***=== or ===***, where each '*' is either 'x' or '.' — the state of the $$$i$$$-th row from the top. Rows ***=== and ===*** alternate, describing the Jenga tower.

Additional constraints on the input: the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^4$$$, and each row of the tower is stable.

Output

For each test case, print Monocarp if Monocarp wins; otherwise, print Polycarp.

Example
Input
4
4
xx.===
===x.x
.xx===
===xxx
2
===x.x
.x.===
3
===xxx
xxx===
===xxx
10
===xxx
x.x===
===xxx
.xx===
===xxx
xx.===
===xxx
x.x===
===xxx
xxx===
Output
Monocarp
Polycarp
Monocarp
Polycarp
Note

In the first test case, Monocarp should remove the central block from the bottom row. After this, it is possible to remove only two blocks from the Jenga tower: the first block from the first row and the third block from the third row. If any other block is removed, the tower falls. Whatever block Polycarp removes, Monocarp takes the other one, leaving Polycarp with no choice.

In the second test case, no blocks can be removed without breaking Jenga. So, Polycarp wins.

In the third test case, Monocarp has a winning strategy.

The fourth test case represents the configuration shown in the picture.