Problem Description

There are $k$ chessboards. Each chessboard is of size $n \times m$ and has exactly 3 positions marked as $0$, with the rest being $1$.

Players A and B take turns to make moves. Each move involves selecting a chessboard and choosing either a row, a column, or both a row and a column to turn all their cells to $0$. However, the move must ensure that at least one cell changes its value before and after the move.

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

Input Format

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

Following this, there are $k$ sets of data, each describing a chessboard:

• The first line of each set contains two positive integers $n$ and $m$, representing the number of rows and columns of the chessboard, respectively, where $1 \le n, m \le 500$.
• The next three lines each contain two positive integers $x$ and $y$, indicating the positions on the chessboard that are marked as $0$. These positions are guaranteed to be unique and within the range $1 \leq x \leq n, 1 \leq y \leq m$.

Output Format

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

Sample Input and Output

Sample Input #1

1
2 3
1 1
2 1
2 2

Sample Output #1

OvO

Sample Input #2

1
4 4
1 1
1 2
4 2

Sample Output #2

QAQ

Notes

Initially, the chessboard looks like this:

011
001

The first player can simply select the first row and second column to turn all cells to zero, leaving the second player with no moves, thus securing a win for the first player.

见题面 Input 部分

见题面 Output 部分