#654 3-Edge

Statement

Statement language

There are $V$ vertices numbered from $1$ to $V$ . You want to add edges to these vertices to construct an undirected graph satisfying all of the following conditions.

No edge connects a vertex to itself.
No two edges connect the same pair of vertices.
Every vertex is incident to exactly $3$ edges.

The graph does not have to be connected.

Construct any graph satisfying these conditions. If no such graph exists, output -1.

Input

The input is given in the following format.

$T$ $V_1$ $V_2$

Output

For each test case, if no graph satisfying the conditions exists, output -1 on a separate line.

Otherwise, output the number of edges $E$ on the first line. On each of the following $E$ lines, output the two endpoints $u$ and $v$ of an edge, separated by a space ( $1 \leq u,v \leq V$ , ).

Constraints

$1 \leq T \leq 500\ 000$ .
$1 \leq V \leq 500\ 000$ .
The sum of $V$ over all test cases is at most .

Subtasks

#	Score	Constraints
1	17	$V \leq 6$ .
2	31	$V$ is a multiple of $4$ .
3	52	No additional constraints.

Samples

Input

Output

In the first three test cases, each vertex has fewer than three other vertices it could connect to, so no valid graph can be constructed.

In the fourth test case, every pair of distinct vertices is connected by an edge. Each vertex is connected to the other three vertices, so every vertex has degree $3$ .

In the fifth test case, connect the vertices in the cycle $1,2,3,4,5,6,1$ , then add the edges $($ , , and . Every vertex is incident to exactly three edges, and there are no self-loops or duplicate edges.