如果一个数字序列中存在某个元素出现超过一次，我们称该序列包含重复元素。形式化地，序列 $(a_1, \dots, a_n)$ 包含重复元素，当且仅当存在两个下标 $i$ 和 $j$ 满足 $i \neq j$ 且 $a_i = a_j$。

给定一个 $n \times n$ 的矩阵 $X$。$X$ 中的每个元素都是 $1$ 到 $n$ 之间的整数（包含 $1$ 和 $n$）。你可以将 $X$ 中的零个或多个元素修改为 $1$ 到 $n$ 之间的任意整数。不同的元素可以被修改为不同的整数。

你的任务是对 $X$ 的元素进行修改，使得以下所有条件成立： 对于每一行 $i$，序列 $(X_{i1}, X_{i2}, \dots, X_{in})$ 包含重复元素。 对于每一列 $j$，序列 $(X_{1j}, X_{2j}, \dots, X_{nj})$ 包含重复元素。

计算实现上述目标所需修改的最少元素个数。此外，请找出一组可行的修改方案。对于每次修改，你需要指定修改哪个元素以及将其修改为哪个值。注意，如果给定的矩阵 $X$ 已经满足上述条件，则需要修改的最少元素个数可以为零。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 1000$)，表示测试用例的数量。接下来是 $t$ 个测试用例。每个测试用例的格式如下：

测试用例的第一行包含一个整数 $n$ ($3 \le n \le 100$)。接下来的 $n$ 行，每行包含 $n$ 个整数。第 $i$ 行的第 $j$ 个整数表示 $X_{ij}$ ($1 \le X_{ij} \le n$)。

所有测试用例中 $n^2$ 的总和不超过 $10\,000$。

输出格式

对于每个测试用例，按以下格式输出修改方案。

第一行输出一个整数 $m$，表示需要修改的最少元素个数。接下来的 $m$ 行，每行输出三个整数 $i$、$j$ 和 $v$。这表示一次修改，即将元素 $X_{ij}$ 修改为 $v$。这三个整数均必须在 $1$ 到 $n$ 的范围内。

如果存在多种解，输出其中任意一种即可。

样例

输入 1

5
4
3 2 1 1
2 1 3 4
1 3 3 1
4 4 4 2
3
1 3 1
2 1 3
3 2 2
5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
3
1 1 2
2 2 1
2 3 2
3
1 1 3
3 2 1
3 1 3

输出 1

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

说明

在第一个测试用例中，修改后的矩阵如下：

$$ \begin{bmatrix} 3 & 2 & 1 & 1 \\ \mathbf{1} & 1 & 3 & 4 \\ 1 & 3 & 3 & 1 \\ 4 & \mathbf{3} & 4 & 2 \end{bmatrix} $$