나눗셈 게임

나눗셈 게임은 두 사람이 번갈아 진행하는 게임이다. 게임판은 양의 정수로 채운 $N \times M$ 행렬이다.

자기 차례가 된 플레이어는 먼저 행 하나를 고른다. 고른 행의 원소가 모두 1이면 그 플레이어가 패배한다. 그렇지 않으면 그 행에서 1보다 큰 원소를 하나 이상 고르고, 고른 원소를 각각 그 수의 약수 중 1이 아닌 값으로 나눈다. 원소마다 다른 약수를 써도 된다. 예를 들어 6은 2, 3, 6으로 나눌 수 있지만 1, 4, 5로는 나눌 수 없다.

행렬을 모든 원소가 1인 상태로 먼저 만든 플레이어가 이긴다. 다시 말해 원소가 모두 1인 행렬을 넘겨받은 플레이어가 진다.

두 사람이 모두 최선으로 둔다고 할 때, 주어진 행렬에서 선수가 이기는지 판정하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $T$는 $100000$ 이하의 양의 정수이다.

각 테스트 케이스의 첫째 줄에는 행의 개수 $N$과 열의 개수 $M$이 주어진다. $N$과 $M$은 모두 $1$ 이상 $50$ 이하이다. 이어지는 $N$개의 줄에는 각각 $M$개의 정수가 주어지고, 이 정수는 모두 $2$ 이상 $10000$ 이하이다.

각 테스트 케이스마다 한 줄에 Case #x: YES 또는 Case #x: NO를 출력한다. $x$는 $1$부터 시작하는 테스트 케이스 번호이고, 선수에게 필승 전략이 있으면 YES, 없으면 NO를 출력한다.