Stefan mastering chess

Task

After having prepared two previous IIOT problems about chess, Stefan has really picked up his chess skills, and he is now ready to give you another chess related challenge!

Today, you are trying to teach your newbie friend about how pieces move and one of your first lessons was about how the queen is the most important piece you want to defend on the board. Given how fast your friend has progressed after having watched videos featuring top grandmasters, you are now ready to give them another challenge!

Now you have given your friend a homework: You gave them several chess positions without kings and the goal is very simple. Find out if the black queen is under threat from any of the white pieces.

After some thinking, the homework was solved fast, but now Stefan gave you a new challenge: Can you emulate your friend's achievement through writing a program which does this for you fast enough to solve several such challenges quickly and correctly?

Here are the rules on how chess pieces move, on the pictures the circles show only the attacked places (take note there are NO kings, so no situations such as pins, checks and checkmate exist -- these positions exist solely for pedagogical purposes, as they wouldn't be valid in actual chess games).

• Pawns can only move forward, one step at a time. In order to capture a piece, they can do it by moving one square forward on the diagonal, if there is a piece of the opposite color there. They will be noted P or p, for white and black pawns respectively.

• Knights can move in every direction, one square in a direction and two in the other direction (or in other words, in an L-shape). They can jump over other pieces and can move to a square as long as the target squares are either empty or occupied by a piece of the opposite color. They will be noted N or n, for white and black knights respectively.
• Bishops move diagonally over the board until they find another piece, which they can capture if it's of the opposite color. They will be noted B or b, for white and black bishops respectively.
• Rooks can move on the line or on the column over the board until they find another piece, which they can capture if it's of the opposite color. They will be noted R or r, for white and black rooks respectively.

• Queens can move on the line, on the column and on the diagonals they are on, until they find another piece, which they can capture if it's of the opposite color. They will be noted Q or q, for white and black queens respectively.

The rest of the $8 \cdot 8$ grid will be given as empty squares, noted with . (dots).

Now find out for each board if the black queen is under attack!

Input data

The first line of the input file contains a single integer $T$, the number of test cases. $T$ test cases follow, each preceded by an empty line.

Each test case consists of $8$ lines, containing $8$ characters each, representing a chess board. The pieces notations have been given in the statement.

Output data

The output file must contain $T$ lines corresponding to the test cases, each consisting of the string YES if the black queen is under attack, or NO otherwise.

Constraints and clarifications

• $1 \le T \le 1000$.
• It is guaranteed that there will be exactly one black queen on the board.
• It is also guaranteed that there will be no pawns in the first and the last row of the board.

Example

stdin

4

........
........
........
........
..q.....
....N...
........
........

........
........
........
.q......
........
........
..R.....
........

........
....B...
........
...p....
.q......
......N.
........
..R.....

........
........
........
........
........
.q......
.p......
.R......

stdout

YES
NO
YES
NO

Explanation

In the first test of the sample case, the knight placed at $(5, 4)$ can attack the queen placed at $(4, 2)$.

You can see below the board for the third test of the sample test case.

Here are the $4$ boards from the sample test.