Consider an n × m chess board, where some cells are legal and some are prohibited. You have many small bishops, so tiny that an unbounded number of them fit in every cell. As expected, bishops can only move diagonally. For every given board description, tell if there is a way to (repeatedly) move as many bishops as needed, never passing a prohibited cell, so that eventually all the legal cells have the same number of bishops.

Input

Input begins with a number t ≥ 0, followed by t cases. Every case begins with the number of rows n and the number of columns m. Follow n lines, each with m items separated with spaces. Prohibited cells are marked with an ‘X’. For legal cells, its initial number of bishops is given. No cell has more than 1000 bishops. Assume 1 ≤ n, m ≤ 100.

Output

For every case, print its number followed by “yes” or “no”, depending on whether it is possible to move the bishops so that eventually all the legal cells have the same number.

Public test cases

**Input**

5 3 9 0 X X X 4 X X X 8 X 1 X 3 X 5 X 7 X X X 2 X X X 6 X X 2 8 X 1 X 1 X 3 X 3 X X 1 X X X 3 X 2 2 X 9 8 X 1 1 X 2 9 500 1000 500 1000 1000 1000 500 1000 500 X X 0 X 0 0 0 500 0

**Output**

Case 1: yes Case 2: no Case 3: no Case 4: yes Case 5: yes

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++ Python
- User solutions
- C++ Python
- Event
- Cinquè Concurs de Programació de la UPC - Final
- Date
- 2007-10-03