(Light and Truth)
The much-anticipated Universal Cup Final is around the corner! Little Cyan Fish is busy preparing the venue for the competition. To make the venue gorgeous, Little Cyan Fish is planning to hang some light bulbs.
Little Cyan Fish has $$$m$$$ wires and plans to connect $$$n$$$ light bulbs using these wires. Each wire needs to connect two distinct bulbs and make all the bulbs form a single connected component. To maintain safety, for any two bulbs there can be at most one wire connecting them directly, and no more than $$$d$$$ wires can be attached to a single bulb.
Once the bulbs are connected, Little Cyan Fish wants to illuminate some of them. Given that active bulbs generate heat, positioning two lit bulbs adjacent to each other could be dangerous. Therefore, if two bulbs are directly connected by a wire, they must not be illuminated at the same time. On the other hand, he doesn't want too few lights on, so he does not want to see an unlit bulb, such that all bulbs directly connected to it are also unlit.
This leads Little Cyan Fish to wonder about the number of different plans to turn on those bulbs to fulfill the requirements. More so, he is keen on finding the optimal way to connect all the light bulbs to maximize the number of the feasible lighting plans.
Given the integers $$$m$$$ and $$$d$$$, your goal is to assist Little Cyan Fish in determining the optimal way to connect $$$n$$$ bulbs using all $$$m$$$ wires, with the intent of maximizing the number of the ways to illuminate the bulbs. Note that you have to determine the value of $$$n$$$ by yourself.
There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \leq T \leq 200$$$), indicating the number of test cases. For each test case:
The first and only line contains two integers $$$m$$$ and $$$d$$$ ($$$2 \le m \le 20$$$, $$$2 \le d \le m$$$).
For each test case:
In the first line, output an integer $$$w$$$ ($$$1 \leq w \leq 2^{m+1}$$$), indicating the maximum number of ways to illuminate the bulbs.
In the second line, output an integer $$$n$$$ ($$$1 \leq n \leq m+1$$$), indicating the number of bulbs Little Cyan Fish should use.
Then output $$$m$$$ lines, where the $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n, u_i \neq v_i$$$) separated by a space, indicating a wire connecting the $$$u_i$$$-th and the $$$v_i$$$-th bulb.
32 25 46 2
2 3 1 2 2 3 5 5 1 2 1 3 2 3 1 4 4 5 7 7 1 2 2 3 3 4 4 5 5 6 6 7
We use colored circles to represent lit bulbs.
For the first sample test case, the $$$2$$$ ways to illuminate the bulbs are illustrated below.
For the second sample test case, the $$$5$$$ ways to illuminate the bulbs are illustrated below.
