TwoFour

Bessie는 TwoFour라는 새로운 2인용 게임을 만들었다. 게임에는 $N$개의 더미($3 \le N \le 30$)가 있고, 각 더미에는 0개에서 4개 사이의 공이 들어 있다. 공의 총합은 $2N$이다.

플레이어는 번갈아 가며 차례를 진행하고, 한 차례에는 올바른 이동 한 번만 한다. 올바른 이동은 다음과 같다. 먼저 플레이어가 서로 다른 더미 두 개를 고른다. 그다음 한 더미에서 공 하나를 꺼내 다른 더미로 옮긴다. 이때 옮겨 받는 더미의 공 개수(새로 들어온 공 포함)가 공을 꺼낸 뒤 보내는 더미에 남은 공 개수보다 많지 않아야 한다.

이동할 수 없으면 게임이 끝난다. 게임이 끝나면 모든 더미에 공이 정확히 2개씩 들어 있다.

승자는 더 많은 더미를 소유한 플레이어다. 더미를 소유한다는 것은, 그 더미에 공이 2개 있고 그 상태가 플레이어가 그 더미로 또는 그 더미에서 마지막으로 한 이동으로 만들어졌다는 뜻이다. 예를 들면 다음과 같다.

• 플레이어가 공 4개인 더미에서 공 1개인 더미로 공 하나를 옮기면, 그 플레이어는 두 번째 더미(이제 공 2개)를 소유한다.
• 플레이어가 공 3개인 더미에서 빈 더미로 공 하나를 옮기면, 그 플레이어는 첫 번째 더미(이제 공 2개)를 소유한다.
• 플레이어가 공 3개인 더미에서 공 1개인 더미로 공 하나를 옮기면, 그 플레이어는 두 더미(둘 다 공 2개)를 모두 소유한다.

소유권은 바뀔 수 있다. 어떤 플레이어가 공 2개인 더미를 소유하고 있다고 하자. 상대가 공 4개인 더미를 골라 공 2개인 더미로 공 하나를 옮기면, 그 더미는 더 이상 누구의 소유도 아니다.

처음부터 공 2개인 더미가 있으면, 그 더미들은 두 플레이어에게 나뉘어 배정된다. 남는 더미가 있으면 2번 플레이어가 소유한다. 플레이어 1이 첫 번째 이동을 한다.

각 초기 상태에 대해, 두 플레이어가 최선을 다할 때의 승자를 구하라. 무승부이면 그 사실을 구하라.

첫 줄에 정수 $N$과 $G$가 주어진다($3 \le N \le 30$, $1 \le G \le 1000$).

다음 $G$줄에는 게임이 하나씩 주어진다. 각 줄에는 공백으로 구분된 정수 $N$개가 있다. 첫 번째 정수는 더미 1의 공 개수, 두 번째 정수는 더미 2의 공 개수이며, 이런 식으로 이어진다. 각 정수는 0 이상 4 이하이다.

$i+1$번째 줄이 게임 $i$를 나타낸다.

$G$줄을 출력한다. $i$번째 줄에는 게임 $i$의 결과를 출력한다. 플레이어 1이 이기면 1, 플레이어 2가 이기면 2, 무승부이면 0을 출력한다.