Batyr came up with a way to play golf on a directed graph, but a directed gaming graph is required for this.
We refer to a directed graph as a gaming graph if:
1. A graph consists of at least 3 vertices, where the first and second vertices are terminal, and there are no outcoming edges from them.
2. Every vertex has precisely two outgoing edges, except the two terminal ones (both edges can lead to the same vertex).
3. There is a path to at least one of the terminal vertices from each vertex in the graph.
In the beginning, Batyr chooses the starting vertex, different from the terminal vertices, in the directed gaming graph and puts there a ball. Then Batyr starts hitting the ball until it lands in one of the terminal vertices. Since Batyr does not play well, he hits the ball so that it goes through one of the two outgoing edges with equal probability and lands in the vertex this edge leads to.
Construct a directed gaming graph consisting of no more than n vertices, and select a starting vertex in it such that the probability of landing in the terminal vertices is equal to a+ba for the first terminal vertex and a+bb for the second.
Input
Each test contains multiple test cases.
The first line contains two integers t and n (1 ≤ t ≤ 100, 33 ≤ n ≤ 100) — the number of test cases and the maximum number of vertices for each set.
The first and only line of each test case contains two integers a and b (1 ≤ a,b ≤ 10^9).
Output
For each test case, print the graph in the following format.
In the first line two integers m,s (3 ≤ m ≤ n, 3 ≤ s ≤ m) - the number of vertices and starting vertex in the graph.
In the each following m − 2 lines print two integers v_i,u_i (3 ≤ i ≤ m, 1 ≤ v_i,u_i ≤ m) - end vertices outgoing from the vertex i.
The probability of landing in the vertex 1 starting from vertex s should be a+ba.
The probability of landing in the vertex 2 starting from vertex s should be a+bb.
There should be a path from each vertex to at least one of the terminal vertices.