W. Cactus Constructive
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Franklin loves cactus graphs and wants you to construct a special cactus for him. In particular, he wants you to construct a tree (a cactus with no cycles) satisfying the following constraint.

For a fixed tree, define $$$f(k)$$$ to be the number of unordered pairs of vertices whose distance between them is exactly $$$k$$$. Franklin gives you three integers $$$x$$$, $$$y$$$, and $$$z$$$. Construct any tree satisfying $$$$$$ f(x)=f(y)=f(z) \gt 0. $$$$$$

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

Input

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

The only line of each test case contains three integers $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1\le x \lt y \lt z\le 100$$$).

Output

For each test case, first output a single integer $$$n$$$ ($$$1\le n\le 10^4$$$) — the number of vertices in your tree.

Then output $$$n-1$$$ lines describing the edges of the tree. Each line should contain two integers $$$u$$$ and $$$v$$$ ($$$1\le u,v\le n$$$, $$$u\ne v$$$), meaning that there is an edge between vertices $$$u$$$ and $$$v$$$.

The printed graph must be a tree, and it must satisfy $$$f(x)=f(y)=f(z) \gt 0$$$.

If there are multiple valid answers, output any of them.

Example
Input
2
1 3 5
1 3 5
Output
12
1 2
2 3
3 4
4 5
5 6
6 7
1 8
4 9
4 10
7 11
7 12
12
1 2
2 3
3 4
4 5
5 6
6 7
1 8
4 9
4 10
7 11
7 12
Note

The two sample tests are identical. The sample output is shown below.

Here, $$$f(1) = f(3) = f(5) = 11$$$. For example, the distance between nodes $$$6$$$ and $$$7$$$ is $$$1$$$, and the distance between nodes $$$8$$$ and $$$9$$$ is $$$5$$$.