The objective of this program is given a configuration of the board to find out if the king is in check or not.

Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.

The objective of this program is given a configuration of the board to find out if the king is in check or not.

Each player begins the game with sixteen pieces: one king, one queen, two rooks, two knights, two bishops, and eight pawns, each of these types of pieces moving differently. Pieces are used to attack and capture the opponent's pieces. The object of the game is to checkmate the opponent's king by placing it under threat of capture ("check") which cannot be avoided.

Input

The first line of input contains the number of test cases. In each case the first line has two numbers representing the amount of white and black pieces. Subsequent lines contain a letter that represents the piece and its corresponding coordinate. Consider that the king is always in first line.

Output

he output consists of a single line answering whether or not the King is in check, consider that your pieces are white and it is your turn.

Example

Input:
3
1 1
K f 8
K a 1
1 2
K f 8
B e 7
K e 2
1 2
K h 8
B f 6
K a 1

Output:
No Check
Check
No Check