This is an interactive problem.

Madeline is playing with a pointless machine. The pointless machine has a hidden tree of size $$$n$$$, and Madeline has to find the edges of the tree by asking the machine.

In a query, Madeline will give the machine a permutation $$$p$$$ of $$$[1,2,\ldots,n]$$$, and the machine will return a sequence $$$q_1, q_2, \ldots, q_n$$$, where $$$q_i$$$ is the number of edges of the induced subgraph formed by the vertices $$$\{p_1,p_2,\ldots,p_i\}$$$.

Here, an induced subgraph of a graph $$$G(V,E)$$$ formed by a subset of vertices $$$V' \subseteq V$$$, is a graph consisting of vertices from this subset and all edges between vertices from subset that are present in original graph $$$G$$$.

However, the machine works slowly, so Madeline can only get the results at once after all queries are completed. The memory of this machine is not very large either, so Madeline can only ask $$$31$$$ times. She doesn't know how to solve it, so she invited you to help her.

Note that the interactor is non-adaptive. That is, tree is fixed in advance and doesn't change with your queries.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The only line of each test case contains a single integer $$$n$$$ ($$$3\le n\le 5\cdot 10^4$$$) — the size of the tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot 10^4$$$.

Interaction

The interaction begins by reading the integer $$$n$$$.

Then, output a single integer $$$k$$$ ($$$1 \leq k \leq 31$$$) — the number of queries.

To ask a query, output a line in the following format:

$$$p_{i,1}\,p_{i,2}\,\ldots\,p_{i,n}$$$ ($$$1 \leq p_{i,j} \leq n$$$, the $$$p_{i,j}$$$ are distinct for each $$$i$$$) — a query described above.

Once you've asked all $$$k$$$ queries, read $$$k$$$ lines of $$$n$$$ integers $$$q_{i,j}$$$ — the responses to the queries as described above.

When you know the hidden tree, output $$$n-1$$$ lines in the following format:

$$$u,v$$$ ($$$1\leq u,v\leq n$$$) — an edge $$$(u,v)$$$ in the hidden tree.

Then, move on to the next test case, or terminate the program if there are no more test cases.

After printing all $$$k$$$ queries do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict.

If, at any interaction step, you read $$$-1$$$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

Hacks

To hack, use the following format.

The first line should contain a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$).

The second line of each test case should contain a single integer $$$n$$$ ($$$3 \le n \le 5\cdot 10^4$$$).

$$$i$$$-th out of next $$$n - 1$$$ lines should contain two integers $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$).

Given edges should form a tree, and the sum of $$$n$$$ over all test cases shouldn't exceed $$$5 \cdot 10^4$$$.

$$$^{\text{∗}}$$$To flush, use:

fflush(stdout) or cout.flush() in C++;
sys.stdout.flush() in Python;
see the documentation for other languages.

Note

Visualizer link

For the first test case:

The first query has answer 0 1 2, since only edge $$$(1, 2)$$$ is in the induced subgraph formed by $$$\{1,2\}$$$.
The second query has answer 0 0 2, since no edges are in the induced subgraph formed by $$$\{1,3\}$$$.

For the third test case:

Edges $$$(2,3)$$$, $$$(3,4)$$$, and $$$(4,1)$$$ are in the induced subgraph formed by $$$\{1,2,3,4\}$$$, so $$$q_{1,4}=3$$$.

Pointless Machine

Examples