A. Everfree Forest
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Everfree Forest, located in the northwestern Equestrian Wasteland, is a large expanse of woodland that has yet to be exposed to megaspell radiation.

To learn Everfree Forest from a scientific perspective, Twilight Sparkle considers it as an undirected connected graph of $$$n$$$ vertices without self-loop and multiple edges, the degree of vertex in which is no more than $$$3$$$.

After field exploration, Twilight Sparkle believes there are exactly $$$k$$$ 3-degree vectices in this graph.

Now she wants to know, what's the maximal edges the graph could have, and what about the minimal edges?

Input

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

Each testcase contains only one line, two integers $$$n,k\ (0\le k \lt n,6\le n\le 10^5,\sum n\le 10^5)$$$.

Output

For each testcase:

The fisrt line contains a single integer $$$m_1$$$ - the maximal edges it could has.

The next $$$m_1$$$ lines, each line contaions two integer $$$u_i,v_i$$$ - the edges in it.

The next line contains a single integer $$$m_2$$$ - the minimal edges it could has.

Then next $$$m_2$$$​ lines, each line contaions two integer $$$w_i,p_i$$$ - the edges in it.

You should make sure that the graph you output is an undirected connected graph of $$$n$$$ vertices without self-loop and multiple edges.

If there are multiple solutions, just output any of them, it could be proved that there exits at least one solution.

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

There are valid solutions of the test case.

maximal edges in testcase 1minimal edges in testcase 1maximal edges in testcase 2minimal edges in testcase 2