问题描述

背景

Tom 从老师那里得到了一个谜题：老师展示了 $42$ 个国际象棋棋盘，每个棋盘被移除了两个方格。老师想知道哪些棋盘可以被 $31$ 个多米诺骨牌完全覆盖。他承诺给正确解决问题的人十块巧克力。Tom 很喜欢巧克力，但他自己无法解决这个问题，于是向他哥哥 John 求助。John（同样喜欢巧克力）同意了，条件是分得一半的奖励。

John 更擅长编程而非思考，因此决定编写一个程序来解决这个问题。你能帮助 John 吗？虽然你不会赢得任何巧克力，但这可能帮助你在编程竞赛中获胜。

问题

给定 $31$ 个多米诺骨牌和一个$8×8$的棋盘，棋盘上移除了两个不同的方格。棋盘的行和列分别用 $a$ 和 $b$ 表示，其中 $a,b∈{1,…,8}$。

一个 $2×1$ 的多米诺骨牌可以水平或垂直放置在棋盘上，因此它可以覆盖以下两种方格组合之一：

水平放置：${(a,b),(a,b+1)}$，其中 $a∈{1,…,8}$,$b∈{1,…,7}$

垂直放置：${(b,a),(b+1,a)}$，其中 $a∈{1,…,8}$，$b∈{1,…,7}$

目标是判断移除两个方格后的棋盘是否可以被 31 个多米诺骨牌完全覆盖。

例如，如果移除的方格是$(8,4)$ 和 $(2,5)$，则可以完全覆盖（如图 1 所示）。

输入

第一行输入包含场景数 $k$。接下来的 $k$ 行，每行包含四个整数 $a$,$b$,$c$,$d$，用空格分隔。这些整数的范围是 ${1,…,8}$，表示被移除的两个方格 $(a,b)$ 和 $(c,d)$。保证 $(a,b)≠(c,d)$

输出

每个场景的输出以一行 "Scenario #i:" 开头，其中 i是场景编号（从 $1$ 开始）。如果可以完全覆盖，则输出 $1$，否则输出 $0$。每个场景的输出以空行结束。

示例输入 1

复制

3
8 4 2 5
8 8 1 1
4 4 7 1

示例输出 1

复制

Scenario #1:
1

Scenario #2:
0

Scenario #3:
0

来源

TUD Programming Contest 2005, Darmstadt, Germany