位运算自动机（bitwise automaton）是一个有向无环图，其顶点称为状态。它有两个终止状态，分别称为 0 和 1，以及任意数量的其他状态，这些状态从 2 开始用连续的整数编号。终止状态没有出边。每个非终止状态恰好有两条出边，一条标记为 0，另一条标记为 1。此外，每个非终止状态 $i$ 都关联一个位编号 $b_i$，并且其中一个状态（终止状态或非终止状态）被指定为起始状态。

位运算自动机对整数输入 $x$ 的求值方式如下：首先，将标记置于起始状态。当标记处于非终止状态 $i$ 时，执行以下操作：检查 $x$ 的第 $b_i$ 位，并沿着对应标签的出边移动到下一个状态。位从 0 开始由低到高编号：第 0 位是 $x$ 的奇偶校验位，依此类推。最终，标记将到达一个终止状态，该状态的编号（0 或 1）即为给定 $x$ 的求值结果。

给定一个自动机对所有从 $0$ 到 $n-1$ 的输入的期望求值结果，你需要构造一个状态数最少的自动机，使其产生这些求值结果。

输入格式

输入包含多个测试用例。第一行包含测试用例数量 $t$，$1 \le t \le 510$。 每个测试用例由两行描述。第一行包含一个整数 $n$，$1 \le n \le 8$。第二行包含 $n$ 个整数，每个整数为 0 或 1，表示输入 $0, 1, \dots, n-1$ 的期望求值结果。

输出格式

按顺序输出每个测试用例的结果。对于每个测试用例，首先在单独的一行中输出自动机的状态数 $m$ ($m \ge 2$)。这必须是产生期望结果的自动机的最小可能状态数。

接下来的 $m-2$ 行按顺序描述从 2 到 $m-1$ 的状态。每行用三个整数描述一个状态：位编号 $b_i$ ($0 \le b_i \le 2$)，标记为 0 的边指向的状态编号，以及标记为 1 的边指向的状态编号。

最后一行输出起始状态的编号。

如果存在多种可能的解，输出任意一个即可。

样例

样例输入 1

1
5
1 0 0 0 1

样例输出 1

4
0 3 0
1 1 0
2