该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

贪吃佘最近收到了一份特殊的礼物：一个长度为 $n$ 的正整数序列 $a_1,a_2,\dots,a_n$。

在贪吃佘看来，一个序列足够"清爽"，当且仅当任意相邻的两个数都没有大于 $1$ 的公共因子。也就是说，对每个满足 $2 \le i \le n$ 的位置，都应当有 $\gcd(a_{i-1},a_i)=1$。

其中 $\gcd(u,v)$ 表示整数 $u$ 和 $v$ 的最大公约数。

为了把这份礼物整理成自己喜欢的样子，贪吃佘可以进行若干次修改。

每次修改时，他需要选择两个不同的位置 $i,j$，并准备两个正整数 $x,y$，满足 $1 \le x,y \le 2\cdot 10^9$。

设操作前这两个位置上的数为 $a_i,a_j$。本次操作合法，当且仅当：$\min(a_i,a_j)=\min(x,y)$ 也就是说，操作前后这两个数的较小值作为一个数值必须保持不变。

注意:这个较小值不要求仍然位于原来的位置；如果操作前 $a_i=a_j$，则操作后只需要 $x,y$ 中至少有一个数仍等于该值即可。

随后，将 $a_i$ 修改为 $x$，将 $a_j$ 修改为 $y$。

现在，贪吃佘想知道如何在不超过 $n$ 次操作内，将整个序列变成"清爽"的序列。

可以证明，对于任意合法输入，答案一定存在。

Format

Input

第一行给出一个整数 $t$，表示共有多少组测试数据，其中 $1 \le t \le 10,000$。

接下来依次描述每组测试数据。

对于每组测试数据，第一行包含一个整数 $n$，表示贪吃佘收到的序列长度，其中 $2 \le n \le 10^5$。

第二行包含 $n$ 个正整数 $a_1,a_2,\dots,a_n$，表示这份礼物最初的样子，其中 $1 \le a_i \le 10^9$。

保证所有测试数据中，$n$ 的总和不超过 $2 \cdot 10^5$。

Output

对于每组测试数据，先输出一个整数 $k$，表示你打算进行的操作次数，其中 $0 \le k \le n$。

注意，$k$ 不需要尽可能小，只要不超过 $n$ 且最终能得到一个"清爽"的序列即可。

接下来的 $k$ 行中，每行输出四个整数 $i,j,x,y$，表示一次操作：选择下标 $i$ 和 $j$，并将 $a_i$ 改为 $x$，将 $a_j$ 改为 $y$。

你的输出需要满足 $1 \le i,j \le n$，$i \ne j$，$1 \le x,y \le 2 \cdot 10^9$，并且这次操作必须合法，也就是操作前的 $a_i,a_j$ 与操作后的 $x,y$ 满足 $\min(a_i,a_j)=\min(x,y)$。

如果存在多种可行方案，输出任意一种即可。

Samples

2
5
9 6 3 11 15
3
7 5 13

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

Note

来看第一组测试数据。

一开始，序列为 $a=(9,6,3,11,15)$。

第一次操作选择位置 $1$ 和位置 $5$，把 $a_1$ 改成 $11$，把 $a_5$ 改成 $9$。这次操作是合法的，因为操作前较小的数是 $9$，操作后较小的数也是 $9$，即 $\min(9,15)=\min(11,9)=9$。

此时序列变为 $a=(11,6,3,11,9)$。

第二次操作选择位置 $2$ 和位置 $5$，把 $a_2$ 改成 $7$，把 $a_5$ 改成 $6$。这次操作同样合法，因为 $\min(6,9)=\min(7,6)=6$。

最终序列变为 $a=(11,7,3,11,6)$。可以检查，任意相邻两个数的最大公约数都等于 $1$，因此它已经是"清爽"的序列。

对于第二组测试数据，原序列本身就已经满足要求，所以不需要进行任何操作。