题目描述

我们称一个长度为 $m$ 序列 $b$ 是好的，当且仅当对于每一个二元组 $i,j \in [1,m]$，都有 $\min(b_i,b_j) | \max(b_i,b_j)$。

其中 $|$ 表示整除，即 $a|b$ 表示 $a$ 被 $b$ 整除。

接下来给定一个长度为 $n$ 的序列 $a$。

你可以对他进行以下操作：

• 选择 $i(1 \le i \le n)$ 和一个非负整数 $x(0 \le x \le a_i)$，将 $a_i$ 变成 $a_i+x$。

• 你应该保证在操作后 $a_i \le 10^{18}$。

你需要使用最多 $n$ 个操作，使得 $a$ 序列成为一个好的序列，可以证明一定是可以构造出来的。

请输出构造方案。

输入格式

第一行一个正整数 $t(1 \le t \le 10^4)$，表示数据组数。

对于每组数据：

第一行一个正整数 $n(1 \le n \le 10^5)$ 表示序列的长度。

接下来 $n$ 个正整数 $a_1,a_2,\dots,a_n(1 \le a_i \le 10^9)$。

输出格式

对于每组数据：

第一行一个整数 $p(0 \le p \le n)$，表示解决方案的操作数。

接下来 $p$ 行，每行两个用空格分开的整数 $i$ 和 $x$。

不需要最小化方案数。

样例

4
4
2 3 5 5
2
4 8
5
3 4 343 5 6
3
31 5 17

4
1 2
1 1
2 2
3 0
0
5
1 3
1 4
2 1
5 4
3 7
3
1 29
2 5
3 3