Problem Description

:::epigraph Lux et Veritas

(Light and Truth) :::

The much-anticipated Universal Cup Finals are coming soon. Xiaoqingyu is busy preparing the competition venue. To make the venue colorful and dazzling, Xiaoqingyu plans to hang some light bulbs.

Xiaoqingyu has $m$ wires and wants to use them to connect $n$ bulbs. Each wire must connect two different bulbs, and all bulbs must form a connected component. For safety, there can be at most one wire directly connecting any pair of bulbs, and each bulb can be connected to at most $d$ wires.

After connecting the bulbs, Xiaoqingyu wants to turn on some of them. Since lit bulbs generate heat, it may be dangerous to have two adjacent bulbs lit at the same time. Therefore, if two bulbs are directly connected by a wire, they cannot be lit simultaneously. On the other hand, he also does not want too few lights, so he does not want to see a bulb that is off while all bulbs directly connected to it are also off.

Xiaoqingyu is very curious: under these constraints, how many different ways are there to light these bulbs? In addition, he wants to find a way to connect all bulbs such that the number of lighting plans is maximized.

Given integers $m$ and $d$, your goal is to help Xiaoqingyu determine the best way to use all $m$ wires to connect $n$ bulbs so that the number of ways to light the bulbs is maximized. Note that you need to choose the value of $n$ by yourself.

Input Format

There are multiple test cases. The first line contains an integer $T$ ($1 \leq T \leq 200$), denoting the number of test cases. For each test case:

The first line contains two integers $m$ and $d$ ($2 \le m \le 20$, $2 \le d \le m$).

Output Format

For each test case:

The first line outputs an integer $w$ ($1 \leq w \leq 2^{m+1}$), meaning the maximum possible number of ways to turn on the bulbs.

The second line outputs an integer $n$ ($1 \leq n \leq m+1$), meaning the number of bulbs Xiaoqingyu needs to use.

Then output $m$ lines. In the $i$-th line, output two integers $u_i$ and $v_i$ separated by a single space ($1 \le u_i, v_i \le n$, $u_i \neq v_i$), representing a wire connecting the $u_i$-th bulb and the $v_i$-th bulb.

3
2 2
5 4
6 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

Hint

We use colored circles to represent bulbs that are turned on.

For the first sample testdata, the $2$ lighting plans are shown in the figure below.

:::align{center} :::

For the second sample testdata, the $5$ lighting plans are shown in the figure below.

:::align{center} :::

Translated by ChatGPT 5