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]. $$$$$$

Serval and Final MEX

Examples