Description

数独是一种经典的逻辑游戏，目标是在 9×9 的网格中填入数字 1-9，使得满足以下条件：

• 每一行都包含 1-9 的所有数字，且不重复；

• 每一列都包含 1-9 的所有数字，且不重复；

• 每一个 3×3 的宫（共 9 个）也都包含 1-9 的所有数字，且不重复。

现在，请你编写一个程序，读取一个已经填好的数独，判断它是否是一个合法的数独解。

Format

Input

第一行包含一个整数 T（1 ≤ T ≤ 100），表示待验证的数独个数。

每个数独由 9 行组成，每行 9 个整数（1-9），数字之间用一个空格分隔。

Output

对于每个数独，如果合法，输出一行 "Yes"，否则输出一行 "No"。

Samples

2
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 1

Yes
No

解释

第一个数独满足所有规则，输出 "Yes"。

第二个数独右下角出现了两个 1，不满足规则，输出 "No"。

Limitation

1s, 1024KiB for each test case.