The game tic-tac-toe is played on a ~3 \times 3~ grid. Two players places cross (
X) and nought (
O) alternatively. The game ends whenever a player can make a line of 3 of their mark vertically, horizontally, or diagonally; or all slots are occupied.
In this problem, you are given a snapshot of a game and you need to verify if it is valid. You can assume that the first mark to be placed is always a cross.
The first input is a number ~T~ specifying the number of test cases ~(1 \le T \le 20\,000)~. For each test case, ~9~ characters on each line are used to denote a snapshot, each containing only
. (period, representing an empty slot),
O. The first 3 characters are the contents of the first row, the next 3 are for the second row, etc. For example, the snapshot of the example is represented as follows:
For each test case, output
yes if the snapshot is valid;
4 ......... ..O...X.. ..OO..X.. OOOXXX...
yes yes no no