M. Roots of Exclusion
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of integers $$$m$$$ of length $$$n$$$.

You have to construct a rooted tree of $$$n$$$ nodes, such that for each node $$$x$$$, $$$m_x$$$ is equal to the mex of the nodes in the subtree of $$$x$$$. In other words, if we take the set of nodes in the subtree of node $$$x$$$, the mex(minimum excluded value) of this set should be equal to $$$m_x$$$.

Note that the tree should be $$$0$$$-indexed, the nodes should be numbered from $$$0$$$ to $$$n-1$$$.

Input

The first line contains a single integer $$$tc \: (1 \le tc \le 10^5)$$$— the number of testcases.

The first line of each testcase contains a single integer $$$n \: (1 \le n \le 10^5)$$$.

The second line of each testcase consists of $$$n$$$ integers $$$m_i \: (0 \le m_i \le n)$$$.

It is guaranteed that there exists at least one solution for each tesctase.

It is guaranteed that the sum of $$$n$$$ overall testcases doesn't exceed $$$10^5$$$.

Output

For each testcase, print $$$n$$$ lines.

On the first line print a single integer $$$root \: (0 \le root \le n-1)$$$ — the root of the tree.

On each of the next $$$n-1$$$ lines, print two integers $$$u,v \: (0 \le u,v \le n-1)$$$ — the edges of the tree.

If there are many answers, print any.

Example
Input
2
4
2 0 4 0
4
1 4 0 0
Output
2
0 1
0 3
2 0
1
0 1
1 3
3 2