불완전한 체스판

$8 \times 8$ 크기의 체스판에서 서로 다른 두 칸이 제거되었다. $r$행 $c$열에 있는 칸을 $(r, c)$로 나타내며, $r, c \in \{1, \dots, 8\}$이다.

$2 \times 1$ 크기의 도미노는 가로 또는 세로로 놓을 수 있다. 즉 두 칸 $\{(a, b), (a, b+1)\}$ 또는 $\{(b, a), (b+1, a)\}$를 덮으며, 여기서 $a \in \{1, \dots, 8\}$, $b \in \{1, \dots, 7\}$이다.

이렇게 두 칸이 제거된 체스판을 $31$개의 도미노로 빈틈없이, 겹치지 않게 완전히 덮을 수 있는지 판별하라.

예를 들어 $(8, 4)$와 $(2, 5)$가 제거된 경우에는 $31$개의 도미노로 판을 완전히 덮을 수 있다.

첫째 줄에 시나리오의 수 $k$가 주어진다. 이어지는 $k$개의 각 줄에는 네 정수 $a$, $b$, $c$, $d$가 공백 하나로 구분되어 주어진다. 이 정수들은 모두 $\{1, \dots, 8\}$ 범위이며, 체스판에서 칸 $(a, b)$와 $(c, d)$가 제거되었음을 뜻한다. $(a, b) \neq (c, d)$임이 보장된다.

각 시나리오마다 먼저 Scenario #i: 형태의 줄을 출력한다. 여기서 $i$는 $1$부터 시작하는 시나리오 번호이다. 그다음 줄에는 해당 체스판을 $31$개의 도미노로 완전히 덮을 수 있으면 $1$을, 그렇지 않으면 $0$을 출력한다. 연속된 시나리오 사이는 빈 줄로 구분한다.