Division Game

Division game is a game for two players. The board is an $N \times M$ matrix of positive integers.

The players move in turns. The player to move first picks one row. If every entry of that row is 1, that player loses. Otherwise the player picks at least one entry greater than 1 from that row and divides each picked entry by one of its own divisors other than 1. Different entries may use different divisors. For example, 6 can be divided by 2, 3 and 6, but it cannot be divided by 1, 4 or 5.

The player who first turns every entry of the matrix into 1 wins. In other words, the player who is handed a matrix of all 1s loses.

Both players play as well as they can. Given the matrix, decide whether the first player wins.

The first line has the number of test cases $T$, a positive integer at most $100000$.

The first line of each test case has the number of rows $N$ and the number of columns $M$, both between $1$ and $50$ inclusive. Each of the next $N$ lines has $M$ integers, and every one of those integers is between $2$ and $10000$ inclusive.

For each test case, print one line holding Case #x: YES or Case #x: NO, where $x$ is the test case number starting from 1. Print YES when the first player has a winning strategy and NO when the first player does not.