There are $k$ boards. Each board is of size $n \times m$, with 3 positions containing 0 and the rest containing 1.

Players A and B take turns. In each turn, a player must choose a board and select a row, a column, or both a row and a column, and set all cells in the selected row/column to 0. The move must ensure that at least one cell on the board changes its value from 1 to 0.

The player who cannot make a move loses. Determine if the first player has a winning strategy.

Input

The input is read from standard input.

The first line contains a positive integer $k$, representing the total number of boards, where $1 \le k \le 10^{5}$.

Each of the next $k$ sets of data consists of 4 lines describing the $i$-th board:

• The first line contains two space-separated positive integers $n$ and $m$, representing the number of rows and columns of the board, where $1 \le n, m \le 500$.
• The next 3 lines each contain two space-separated positive integers $x$ and $y$, representing the position of a 0 on the board. It is guaranteed that these positions are distinct and $1 \le x \le n, 1 \le y \le m$.

Output

Output to standard output.

If the first player has a winning strategy, output the string OvO. Otherwise, output the string QAQ.

Examples

Input 1

1
2 3
1 1
2 1
2 2

Output 1

OvO

Note 1

Initially, the board is:

011
001

The first player can choose the first row and the second column to set all cells to 0. The second player then has no moves, so the first player wins.

Input 2

1
4 4
1 1
1 2
4 2

Output 2

QAQ