Gomoku, also known as 五子棋, is a kind of board game with the following rules.
Players alternate turns to place a stone of their color on an empty intersection. Black plays first. The winner is the first player to form an unbroken chain of five stones horizontally, vertically, or diagonally. And the game will stop immediately if someone wins the game.
MM loves playing Gomoku with his friends(if there are any), but his friends found it boring playing with him.
Therefore, it is not surprising for his friends to play the Gomoku indifferently, and they may ignore the rules of the Gomoku sometimes.
So MM played \(T\) games of Gomoku today, and you are given the results of these \(T\) games of Gomoku.
For each game, please tell him whether the result of this game can be generated through some valid game processes, or someone who played this game wasn't paying attention to the rules.
Note that MM and his friend may not finish the game, so it should be considered valid even if there's no winner.
Hint:
Hint1: Testcases 1-2: The number of black stones and the number of white stones should be equal; or the number of black stones should be equal to the number of white stones plus 1.
Hint2: Testcases 3-4: There should be only 1 winner at any moment. If the black stone has 5-in-a-row, the white stone should not have any 5-in-a-row; otherwise, the board should be declared illegal; vice versa.
Another Hint
The first thing to check is whether the difference between the number of black and white stones are at most 1. And the number of black stones can't be less than the number of white stones.
The second step is to check whether there's at most one winner, and the winner should be the one who placed the last stone (we could know that from the number of stones each player placed). If not, it is clear that this result is illegal. On the other hand, if there's no winner, it is clear that it's legal.
So now we're facing the case that there's exactly 1 winner. To ensure that the game ends right after someone wins, we can iterate thru all possible "last placed stone". A stone can be the "last placed stone" if and only if the color of this stone is the same as the winner's color. And before the stone was placed, there should be no winner. The result is considered legal if there exists at least 1 valid "last placed stone", or illegal otherwise.
Input
The first line contains an integer T, which is guaranteed to be less than or equal to 20.
The following are the result of each game, where each game is represented by a 15 x 15 board which contains {'0', '1', '2'} only.
'0' means that the grid has not been placed any stone, '1' means that the grid is placed with the first player's stone, '2' means that the grid is placed with the second player's stone.
It is guaranteed that in 2/6 of the testdata, there's no winner.
It is guaranteed that in 4/6 of the testdata, there's no more than two 5-in-a-row.
There's no further constraints in the last 2/6 of the testdata.
Output
For each game, print "Yes\n" if the result can be generated through some valid game processes, or "No\n" otherwise.