No submission language available for this problem.

Description

Input

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 30\,000$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 500$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$)  — the initial array.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $250\,000$.

Output

For each test case print answer in the following format.

If you cannot turn the array into a concatenation of tandem repeats, print a single integer $-1$.

Otherwise print the number of operations $q$ ($0 \le q \le 2 \cdot n^2$) that you want to do. Then print the descriptions of operations.

In each of the following $q$ lines print two integers $p$ and $c$ ($1 \le c \le 10^9$), which mean that you insert the integer $c$ twice after $p$ elements of the array. If the length of the array is $m$ before the operation, then the condition $0 \le p \le m$ should be satisfied.

Then you should print any way to split the resulting array into tandem repeats. First, print a single integer $d$, and then print a sequence $t_1, t_2, \ldots, t_d$ of even integers of size $d$ ($d, t_i \ge 1$). These numbers are the lengths of the subsegments from left to right.

Note that the size of the resulting array $a$ is $m = n + 2 \cdot q$. The following statements must hold:

• $m = \sum\limits_{i = 1}^{d}{t_i}$.
• For all integer $i$ such that $1 \le i \le d$, the sequence $a_l, a_{l+1}, \ldots, a_r$ is a tandem repeat, where $l = \sum\limits_{j = 1}^{i - 1}{t_j} + 1$, $r = l + t_i - 1$.

It can be shown that if the array can be turned into a concatenation of tandem repeats, then there exists a solution satisfying all constraints. If there are multiple answers, you can print any.

Samples

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

-1
0
1
2
4
1 3
5 3
5 3
10 3
2
8 6 
5
0 3
8 3
5 3 
6 2 
7 1
4
2 6 6 2

Note

In the first test case, you cannot apply operations to the array to make it possible to split it into tandem repeats.

In the second test case the array is already a tandem repeat $[5, 5] = \underbrace{([5] + [5])}_{t_1 = 2}$, thus we can do no operations at all.

In the third test case, initially, we have the following array: $$[1, 3, 1, 2, 2, 3].$$ After the first insertion with $p = 1, c = 3$: $$[1, \textbf{3, 3}, 3, 1, 2, 2, 3].$$ After the second insertion with $p = 5, c = 3$: $$[1, 3, 3, 3, 1, \textbf{3, 3}, 2, 2, 3].$$ After the third insertion with $p = 5, c = 3$: $$[1, 3, 3, 3, 1, \textbf{3, 3}, 3, 3, 2, 2, 3].$$ After the fourth insertion with $p = 10, c = 3$: $$[1, 3, 3, 3, 1, 3, 3, 3, 3, 2, \textbf{3, 3}, 2, 3].$$ The resulting array can be represented as a concatenation of tandem repeats: $$\underbrace{([1, 3, 3, 3] + [1, 3, 3, 3])}_{t_1 = 8} + \underbrace{([3, 2, 3] + [3, 2, 3])}_{t_2 = 6}.$$

In the fourth test case, initially, we have the following array: $$[3, 2, 1, 1, 2, 3].$$ After the first insertion with $p = 0, c = 3$: $$[\textbf{3, 3}, 3, 2, 1, 1, 2, 3].$$ After the second insertion with $p = 8, c = 3$: $$[3, 3, 3, 2, 1, 1, 2, 3, \textbf{3, 3}].$$ After the third insertion with $p = 5, c = 3$ $$[3, 3, 3, 2, 1, \textbf{3, 3}, 1, 2, 3, 3, 3].$$ After the fourth insertion with $p = 6, c = 2$: $$[3, 3, 3, 2, 1, 3, \textbf{2, 2}, 3, 1, 2, 3, 3, 3].$$ After the fifth insertion with $p = 7, c = 1$: $$[3, 3, 3, 2, 1, 3, 2, \textbf{1, 1}, 2, 3, 1, 2, 3, 3, 3].$$ The resulting array can be represented as a concatenation of tandem repeats: $$\underbrace{([3] + [3])}_{t_1 = 2} + \underbrace{([3, 2, 1] + [3, 2, 1])}_{t_2 = 6} + \underbrace{([1, 2, 3] + [1, 2, 3])}_{t_3 = 6} + \underbrace{([3] + [3])}_{t_4 = 2}.$$