说明

$\textit{Chomp!}$ 是一个经典的两人游戏。起始时有一片由 $mn$ 块大小为 $1 \times 1$ 的小块巧克力连为一片的巧克力，形状如 $m \times n$ 的二维数组（其中 $m$ 为行，$n$ 为列），而最左下角的那一小块非常苦涩，大家都想避开。游戏的玩法为轮流拿走巧克力小块，方式是先从剩下来的巧克力挑一小块，并把其右上方（含正上方及正右方）所有小块同时拿掉。到最后谁拿到最左下角的那一小块便输了。

例如起始时有 $3 \times 4$ 的一片巧克力：

:::align{center} :::

若玩家一选择了 $X$ 那一小块，则连带 $Y$ 的那些小块也会被拿掉：

:::align{center} :::

接着由玩家二从剩下的巧克力块选择。若玩家二此时选择了 $W$ 那一小块，则连带 $Z$ 的那些小块也会被拿掉：

:::align{center} :::

按照以上规则，我们不难证明，在游戏中所出现的任何情形，如从左至右输出每一列 (column) 的巧克力小块数，其结果必为一单调递减 (monotonic decreasing) 数列，且对应此数列之形状唯一。如上例的最终状态，其可以数列 $(3, 1, 0, 0)$ 表示。

在此题目中，我们针对 $3 \times n$ 大小巧克力的 $\textit{Chomp!}$ 游戏中出现的各种情况进行分析，目的是计算在当前的情况下，先行者是否有获胜的走法。我们假设游戏双方皆绝顶聪明，会采取最好的游玩策略来让自己获胜。若先行者能获胜，我们输出在目前情况下有多少种可以获胜的第一步选择，并把这些选择枚举出来；反之，则输出 $0$。这里，我们将下面数上来第 $i$ 行、左边数过来第 $j$ 列的小块巧克力编号为 $(i, j)$，满足左下角为 $(1, 1)$，右上角为 $(3, n)$。

输入格式

$$\begin{aligned} &t \\ &n_1 \; p_1 \; q_1 \; r_1 \\ &\vdots \\ &n_t \; p_t \; q_t \; r_t \end{aligned}$$

• $t$ 代表总共有 $t$ 笔询问。
• $n_i$ 代表第 $i$ 笔询问的巧克力总列数。
• $p_i, q_i, r_i$ 代表第 $i$ 笔询问的状态为从左至右先有 $p_i$ 列为 $3$ 小块巧克力，接着有 $q_i$ 列为 $2$ 小块巧克力，再有 $r_i$ 列为 $1$ 小块巧克力。

输出格式

$$\begin{aligned} &c_1 \\ &x_{1,1} \; y_{1,1} \; \dots \; x_{1,c_{1}} \; y_{1,c_{1}} \\ &\vdots \\ &c_t \\ &x_{t,1} \; y_{t,1} \; \dots \; x_{t,c_{t}} \; y_{t,c_{t}} \end{aligned}$$

• $c_i$ 代表在第 $i$ 笔询问的状态下，先行者可以获胜的第一步选择数。若先行者无法获胜，则 $c_i = 0$。
• $x_{i,j}, y_{i,j}$ 代表第 $i$ 笔询问中，第 $j$ 个可以作为先行者获胜的第一步选择的小块巧克力编号。若 $c_i > 1$，请依 $x$ 值小到大排序编号，若 $x$ 值相同则依 $y$ 值小到大排序编号。

4
1 0 0 1
10 1 0 9
3 1 2 0
3 1 1 1

0
1
1 4
2
1 3 2 2
3
1 3 2 2 3 1

1
100 67 22 11

3
1 100 2 59 3 18

提示

数据限制

• $1 \le t \le 1000$。
• $1 \le n_i \le 500$。
• $0 \le p_i, q_i, r_i \le n_i$。
• $1 \le p_i + q_i + r_i \le n_i$。
• 输入的数皆为整数。

评分说明

本题共有三组子任务，条件限制如下所示。 每一组可有一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。

子任务	分数	额外输入限制
1	20	$t = 1$，$p_i = 0$。
2	37	$1 \le n_i \le 50$。
3	43	无额外限制。