This is the simple version of the problem. The difference between the versions is that in this version, you can ask no more than $$$32 \cdot (n + m)$$$ questions, and $$$n \leq 15$$$. You can hack only if you solved all versions of this problem.

This is an interactive problem.

The jury has thought of a directed acyclic graph without loops and multiple edges, which has $$$n$$$ vertices and $$$m$$$ edges.

Your task is to determine which edges are in this graph. To do this, you can ask questions of the form: what does the $$$k$$$-th path look like in the lexicographically$$$^{\text{∗}}$$$ sorted list of all paths in the graph.

A path in the graph is a sequence of vertices $$$u_{1}, u_{2}, \dots, u_{l}$$$, such that for any $$$i \lt l$$$, there exists an edge ($$$u_{i}, u_{i + 1}$$$) in the graph.

Your task is to accomplish this by asking no more than $$$32 \cdot (n + m)$$$ questions.

The interaction for each test case begins with reading the integer $$$n$$$.

Then you can ask up to $$$32 \cdot (n + m)$$$ questions.

To ask a question, output a string in the format "? k" (without quotes) ($$$1 \le k \le 2^{30}$$$). After each question, read an integer $$$q$$$ — the number of vertices in the $$$k$$$-th path. If $$$q = 0$$$, then such a path does not exist; otherwise, read $$$q$$$ integers — the vertex numbers that make up this path.

It can be shown that under the given constraints, the number of distinct paths in the graph does not exceed $$$2^{30}$$$.

To report your answer, first output a string in the format "! m", and then output $$$m$$$ lines describing the edges in the format "u v", which means that there is an edge leading from $$$u$$$ to $$$v$$$. You can output the edges in any order. Outputting the answer does not count as a query.

After printing each query 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:

For hacks, use the following format:

The first line should contain a single integer $$$t$$$ ($$$1\leq t\leq 10$$$) — the number of test cases.

The first line of each case should contain two integers $$$n, m$$$ ($$$1 \leq n \leq 15$$$, $$$0 \leq m \leq \frac{n \cdot (n - 1)}{2}$$$) — the number of vertices and edges in the graph.

The next $$$m$$$ lines should contain descriptions of the edges. Each edge is defined by two integers $$$v$$$, $$$u$$$ ($$$1 \leq v, u \leq n$$$, $$$v \neq u$$$), meaning an edge from vertex $$$v$$$ to vertex $$$u$$$.

The graph cannot contain cycles or multiple edges.