Game

Two players play a game on a table of 0s and 1s with M rows and N columns. Rows are numbered from top to bottom and columns from left to right. The player who moves first is Player 1, and the player who moves second is Player 2. On a turn, a player chooses a rectangular part of the table whose upper left cell contains 1, and flips every number in that part. That is, each 0 becomes 1 and each 1 becomes 0. The first figure shows one move on a 3x4 table A, where a 2x2 part is chosen and flipped to give table B. The thick border marks the chosen part, whose upper left cell is 1. The second figure shows a move where a 2x3 part of a 3x4 table is chosen and flipped. Both players play optimally. The player who turns every number in the table into 0 wins. Given the table, write a program that determines which player wins.

The first line of each test contains two integers M and N, separated by a space. Each of the next M lines contains N numbers, each 0 or 1, separated by spaces. The input consists of several tests, and there are at most 200 tests. Each of M and N is at most 100.

For each test, print 1-r toglogch if Player 1 wins, or 2-r toglogch if Player 2 wins, on a single line.