You are given an array $a$ consisting of $n\ge 4$ non-negative integers.

You need to perform the following operation on $a$ until its length becomes $1$:

• Select two indices $l$ and $r$ ($1\le {\color{red}{ l \lt r }} \le |a|$), and replace the subarray $[a_l,a_{l+1},\ldots,a_r]$ with a single integer $\operatorname{mex}([a_l,a_{l+1},\ldots,a_r])$, where $\operatorname{mex}(b)$ denotes the minimum excluded (MEX)$^{\text{∗}}$ of the integers in $b$. In other words, let $x=\operatorname{mex}([a_l,a_{l+1},\ldots,a_r])$, the array $a$ will become $[a_1,a_2,\ldots,a_{l-1},x,a_{r+1},a_{r+2},\ldots,a_{|a|}]$. Note that the length of $a$ decreases by $(r-l)$ after this operation.

Serval wants the final element in $a$ to be $0$. Help him!

More formally, you have to find a sequence of operations, such that after performing these operations in order, the length of $a$ becomes $1$, and the final element in $a$ is $0$.

It can be shown that at least one valid operation sequence exists under the constraints of the problem, and the length of any valid operation sequence does not exceed $n$.

Note that you do not need to minimize the number of operations.

$^{\text{∗}}$The minimum excluded (MEX) of a collection of integers $b_1, b_2, \ldots, b_k$ is defined as the smallest non-negative integer $x$ which does not occur in the collection $b$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($4\le n\le 5000$) — the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0\le a_i\le n$) — the elements of the array $a$.

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

Output

For each test case, output a single integer $k$ ($0\le k\le n$) in the first line of output — the length of the operation sequence.

Then, output $k$ lines, the $i$-th line containing two integers $l_i$ and $r_i$ ($1\le l_i \lt r_i\le |a|$) — the two indices you choose in the $i$-th operation, where $|a|$ denotes the length of the array before this operation.

If there are multiple answers, you may print any of them.

Note

In the first test case, since $\operatorname{mex}([1,2,3,4])=0$, after the only operation, the array becomes $[0]$.

In the second test case, the array $a$ changes as follows: $$ [\underline{0,1},0,0,1]\to [\underline{2,0},0,1]\to [\underline{1,0},1]\to [\underline{2,1}]\to [0]. $$

In the third test case, the array $a$ changes as follows: $$ [0,0,0,0,\underline{0,0}]\to [0,0,\underline{0,0},1]\to [\underline{0,0},1,1]\to [\underline{1,1,1}]\to [0]. $$