Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 1591
Winlinez

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Sunny Cup 2003 - Preliminary Round

April 20th, 12:00 - 17:00

Problem J: Winlinez


Have you played the game "winlinez"? It's just like gobang. Now we have a board of 9 * 9 grids, on which there are several beads. These beads have only seven colors, we number them 1 - 7. We define the empty grid to be zero. Each turn you can move any bead on the board to the destination where there is a route between them. The route means that the bead can move up, down, left or right to the adjacent empty grid and may go on until it reaches the destination. After the moving, if there are five or more same-colored beads in a line (row, column, diagonal), they will all be eliminated.

For example, in figure 1, we can move the bead at (6, 7) (row, column) to (3, 1). Then the beads at (2, 1) (3, 1) (4, 1) (5, 1) (6, 1) will be wiped off. Now your task is to judge whether we can find an available move which makes for disappearing of some beads on a specified board.

Figure 1. A temporary board in the game "winlinez"


Input

The input data consists of the information of several boards. The first line of the input contains the number of boards.

Before each board description there is a blank line, then followed by nine lines of data. Each line contains 9 integers. Each of them means the color of the corresponsive position of the board.


Output

For each board, you are supposed to output "Yes" or "No" respectively according to the problem description.


Sample Input

1

1 2 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 0 0
6 0 0 3 1 0 0 0 0
6 0 4 0 0 0 0 5 0
6 0 0 0 0 0 6 0 0
0 0 0 3 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 4 0 0 0 0 0


Sample Output

Yes



Author: DU, Peng
Source: Zhejiang University Local Contest 2003, Preliminary
Submit    Status