NC212625. LinkGameofPrimeFactors
描述
Super Brain is a famous scientific reality and talent show aiming to find people with exceptional brainpower.
In one of the challenges called Link Game of Prime Factors, at first, a n × m matrix M composed with different numbers is given to the contestant (as the leftmost picture). After a couple of operations, the contestant will obtain a matrix within lots of spaces (as the rightmost picture).
In the original Link Game (Lian Lian Kan in Chinese), if you can draw at most three horizontal or vertical head-and-tail-connected lines over the empty grids (the lines can be out of the whole area) to connect two non-empty grids with the same symbol or the two non-empty grids with the same symbol are adjacent, then you can change these two grids into empty.
Furthermore, in the Prime Factors Link Game, if you can draw at most three lines over the empty grids with the same prime factor or the two non-empty grids with the same prime factor are adjacent, then you can change these grids with the following regulations, Here shows the picture:
With the ongoing process of the game, it seems more challenging to accomplish the task successfully. More seriously, if some specific grids are wrongly removed in advance by mistake, it is more likely that the entire matrix will eventually become unsolvable.
Because of the time for the contestant to complete the task is very limited, for each state of the whole matrix M, the contestant is eager to know whether the matrix can be solved after lots of operation steps eventually.
Now you are asked to write a program to help them tackle this problem. Given a n × m matrix M composed with different numbers, please help them judge whether all of the non-empty grids that can be removed altogether.
In one of the challenges called Link Game of Prime Factors, at first, a n × m matrix M composed with different numbers is given to the contestant (as the leftmost picture). After a couple of operations, the contestant will obtain a matrix within lots of spaces (as the rightmost picture).
In the original Link Game (Lian Lian Kan in Chinese), if you can draw at most three horizontal or vertical head-and-tail-connected lines over the empty grids (the lines can be out of the whole area) to connect two non-empty grids with the same symbol or the two non-empty grids with the same symbol are adjacent, then you can change these two grids into empty.
Furthermore, in the Prime Factors Link Game, if you can draw at most three lines over the empty grids with the same prime factor or the two non-empty grids with the same prime factor are adjacent, then you can change these grids with the following regulations, Here shows the picture:
- Initially, it's defined that number 0 represents the empty grid.
- If the number of a grid is equal to 1, it'll change into an empty grid 0 automatically.
- If both two linked grids share the same number, you can change these two grids equal to 1, and then change into empty. For instance, such as two linked numbers 11 and 11 shown in the picture, after linking you can change both of them into empty grids.
- If the number of two linked grids is not the same, but share the same Greatest Common Divisor, you can change these two grids both divided by the Greatest Common Divisor at the same time. For instance, such as two linked numbers 9 and 3 shown in the picture, after linking you can change them into 3 and 1, respectively. And then the number 1 will change into an empty grid.
- Otherwise, you cannot change any pair of two linked grids any more, for instance, such as two linked numbers 8 and 7 shown in the picture, because number 8 number and 7 are composed to a coprime pair.
With the ongoing process of the game, it seems more challenging to accomplish the task successfully. More seriously, if some specific grids are wrongly removed in advance by mistake, it is more likely that the entire matrix will eventually become unsolvable.
Because of the time for the contestant to complete the task is very limited, for each state of the whole matrix M, the contestant is eager to know whether the matrix can be solved after lots of operation steps eventually.
Now you are asked to write a program to help them tackle this problem. Given a n × m matrix M composed with different numbers, please help them judge whether all of the non-empty grids that can be removed altogether.
输入描述
There are multiple test cases. The first line of the input contains an integer T (1 ≤ T ≤ 20), indicating the number of test cases.
For each test case, the first line contains two integers n and m (1 ≤ n, m ≤ 10).
In the next n lines, each line contains m integers, j-th number in the i-th line means the original number(0 ≤
输出描述
For each case, output "Yes"(without quotes) if and only if all of the non-empty grids that can be removed altogether. Otherwise, output "No"(without quotes) instead.
示例1
输入:
3 8 8 43 101 4 87 8 7 50 19 3 77 10 8 31 11 11 13 52 26 7 15 33 27 4 85 18 65 4 15 21 43 89 9 71 89 49 26 9 21 13 5 19 9 17 15 5 5 21 60 17 3 8 52 64 11 10 71 29 5 31 88 2 34 52 101 8 8 101 43 1 22 30 1 45 15 66 55 12 121 12 15 55 11 26 64 19 4 26 11 38 96 39 29 66 101 46 43 27 9 27 48 87 32 81 9 22 18 36 5 9 10 44 13 49 103 13 8 78 72 52 6 23 6 9 13 117 110 65 54 103 27 3 3 1 2 3 1 3 2 1 0 0
输出:
Yes No No
说明:
For the second sample, it'll be no solution. Because the number 49 can not be removed.
For the third sample, it's still an unsolvable state. Because you can only draw at most three lines to connect two non-empty grids with the same symbol.
