An array $b$ of $m$ positive integers is good if for all pairs $i$ and $j$ ($1 \leq i,j \leq m$), $\max(b_i,b_j)$ is divisible by $\min(b_i,b_j)$.

You are given an array $a$ of $n$ positive integers. You can perform the following operation:

Select an index $i$ ($1 \leq i \leq n$) and an integer $x$ ($0 \leq x \leq a_i$) and add $x$ to $a_i$, in other words, $a_i := a_i+x$.

After this operation, $a_i \leq 10^{18}$ should be satisfied.

You have to construct a sequence of at most $n$ operations that will make $a$ good. It can be proven that under the constraints of the problem, such a sequence of operations always exists.


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \leq 10^9$) — representing the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test, output a single integer $p$ ($0 \leq p \leq n$) — denoting the number of operations in your solution.

In each of the following $p$ lines, output two space-separated integers — $i$ and $x$.

You do not need to minimize the number of operations. It can be proven that a solution always exists.


-----Examples-----

Input
4
4
2 3 5 5
2
4 8
5
3 4 343 5 6
3
31 5 17
Output
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


-----Note-----

In the first test case, array $a$ becomes $[5,5,5,5]$ after the operations. It is easy to see that $[5,5,5,5]$ is good.

In the second test case, array $a$ is already good.

In the third test case, after performing the operations, array $a$ becomes $[10,5,350,5,10]$, which is good.

In the fourth test case, after performing the operations, array $a$ becomes $[60,10,20]$, which is good.

Difficulty: EASY
Tags: Number theory

Sorting

Implementation

Constructive algorithms
Skill types: Sorting

Starter code:

Solutions:
for s in [*open(0)][2::2]:
	print(len((a := s.split())))
	i = 0
	for x in map(int, a):
		i += 1
		print(i, 2 ** len(f'{x:b}') - x)


import sys
import math
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s.strip())

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	arr = inlt()
	print(n)
	for i in range(n):
		val = int(math.log2(arr[i]))
		print(i + 1, 2 ** (val + 1) - arr[i])


import math
t = int(input())
for j in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(n)
	for i in range(n):
		power = int(math.log(arr[i], 2))
		print(i + 1, 2 ** (power + 1) - arr[i])


import math as mt
MAXN = 10001

def sieve():
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	d = {}
	while x != 1:
		if spf[x] in d:
			d[spf[x]] += 1
		else:
			d[spf[x]] = 1
		x = x // spf[x]
	return d
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	print(n)
	for i in range(n):
		x = int(mt.log(a[i], 2)) + 1
		print(i + 1, pow(2, x) - a[i])


t = int(input())
import math
for z in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(n)
	for i in range(n):
		s = int(math.log(a[i]) / math.log(2)) + 1
		print(i + 1, 2 ** s - a[i])


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	ans = []
	for (i, val) in enumerate(a):
		p = int(math.log(val, 2)) + 1
		d = pow(2, p) - val
		ans.append((i + 1, d))
	print(len(ans))
	for (i, val) in enumerate(ans):
		print(val[0], val[1])


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	steps = []
	for i in range(n):
		l = len('{:b}'.format(arr[i]))
		old = arr[i]
		if 1 << l >= arr[i]:
			arr[i] = 1 << l
		else:
			arr[i] = 1 << l + 1
		if arr[i] > old:
			steps.append((i + 1, arr[i] - old))
	print(len(steps))
	for (i, x) in steps:
		print(i, x)


import sys
from os import path

def input():
	return sys.stdin.readline().strip()

def solve(n, a):

	def f(x):
		p = 2
		while p <= x:
			p *= 2
		return p
	print(n)
	for i in range(n):
		d = f(a[i]) - a[i]
		print(i + 1, d, sep=' ')
		a[i] += d

def main():
	testcases = int(input())
	for _ in range(testcases):
		n = int(input())
		array = list(map(int, input().split()))
		solve(n, array)
if path.exists('Tests'):
	sys.stdin = open('Tests/input_1.txt', 'r')
	sys.stdout = open('Tests/output_1a.txt', 'w')
main()


import math

def solve():
	n = int(input())
	a = list(map(int, input().split())) + [10 ** 10]
	s = sum(a)
	print(n)
	for i in range(n):
		k = int(math.log(a[i], 2))
		print(i + 1, (1 << k + 1) - a[i])
t = int(input())
for i in range(t):
	solve()


from math import log2
test_case = int(input())
for test in range(test_case):
	n = int(input())
	List = list(map(int, input().split()))
	m = min(List)
	M = []
	for i in range(n):
		c = int(log2(List[i])) + 1
		t = 2 ** c
		M.append([i + 1, t - List[i]])
	print(len(M))
	for i in M:
		print(i[0], i[1])


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = 1
	print(n)
	for i in arr:
		print(cnt, end=' ')
		x = 1
		while x <= i:
			x *= 2
		print(x - i)
		cnt += 1
	t -= 1


import sys

def fn(a, l):
	print(l)
	for index in range(l):
		val = bin(a[index])
		calc = (int(bin(2 ** (len(val) - 2) - 1), 2) ^ int(val, 2)) + 1
		print(index + 1, calc)
input = sys.stdin.readlines()
for i in range(int(input[0].strip('\n'))):
	new_list = [int(x) for x in input[2 * i + 2].strip('\n').split(' ')]
	len_list = int(input[2 * i + 1].strip('\n'))
	fn(new_list, len_list)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	Max = L[0]
	L1 = []
	count = n
	for i in range(0, n):
		rec = 1
		while rec <= L[i]:
			rec *= 2
		L1.append((i + 1, rec - L[i]))
	print(count)
	for j in L1:
		print(f'{j[0]} {j[1]}')