D. Do You Want to Build a Christmas Tree?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Of course, you do.

Don't even try to resist it—you can already feel it deep inside: the primal urge to build a Christmas tree. Right here, right now.

But beware: an ordinary Christmas tree will not do. You must build a Special Christmas Tree.

For the purposes of this problem, a Christmas Tree is simply a binary tree— that is, a connected, acyclic graph where each node has degree at most three.

So, what makes it Special?

You are given three integers $$$P$$$, $$$Q$$$, and $$$R$$$.

Suppose your Christmas Tree has $$$N$$$ nodes, labeled $$$1$$$ through $$$N$$$.

The following conditions must hold:

  • There are exactly $$$P$$$ pairs $$$(i, j)$$$, with $$$1 \le i \lt j \le N$$$, such that the distance between node $$$i$$$ and node $$$j$$$ is exactly $$$1$$$.
  • There are exactly $$$Q$$$ pairs $$$(i, j)$$$, with $$$1 \le i \lt j \le N$$$, such that the distance between node $$$i$$$ and node $$$j$$$ is exactly $$$2$$$.
  • There are exactly $$$R$$$ pairs $$$(i, j)$$$, with $$$1 \le i \lt j \le N$$$, such that the distance between node $$$i$$$ and node $$$j$$$ is exactly $$$3$$$.

Here, the distance between two nodes means the number of edges on the unique simple path between them.

Your task is to construct such a Special Christmas Tree, or declare that it is impossible.

Input

The input consists of multiple test cases.

The first line contains an integer $$$T$$$ ($$$1 \le T \le 1000$$$)— the number of test cases.

Each of the next $$$T$$$ lines contains three integers $$$P$$$, $$$Q$$$, and $$$R$$$ ($$$1 \le P \le 10^5$$$, $$$0 \le Q, R \le 10^6$$$) — the designated counts of pairs of nodes at distances $$$1$$$, $$$2$$$, and $$$3$$$, respectively.

The sum of $$$P$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case:

Print a line with a single integer $$$N$$$ — the number of nodes in your tree.

Then print $$$N-1$$$ lines, each with two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le N$$$), denoting an edge between nodes $$$u$$$ and $$$v$$$.

If there are multiple possible trees, output any of them.

If no Special Christmas Tree exists, output $$$-1$$$.

Example
Input
3
2 1 0
5 6 4
3 7 1
Output
3
1 2
2 3
6
1 2
2 3
2 4
1 5
1 6
-1
Note

The Special Christmas Tree for the second test case can be visualized as:

Figure D.1: Example of the Christmas tree for the second test case.

There are $$$5$$$ node pairs with distance $$$1$$$: $$$(1,2)$$$, $$$(2,3)$$$, $$$(2,4)$$$, $$$(1,5)$$$, and $$$(1,6)$$$.

There are $$$6$$$ node pairs with distance $$$2$$$: $$$(1,3)$$$, $$$(1,4)$$$, $$$(2,5)$$$, $$$(2,6)$$$, $$$(3,4)$$$, and $$$(5,6)$$$.

There are $$$4$$$ node pairs with distance $$$3$$$: $$$(3,5)$$$, $$$(3,6)$$$, $$$(4,5)$$$, and $$$(4,6)$$$.