This is the hard version of the problem. The difference between the versions is that in this version, you can ask no more than (n + m) questions, and (n \leq 30). 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 (n + m) questions. (^{\text{∗}})A sequence (a) is lexicographically smaller than a sequence (b) if and only if one of the following holds: (a) is a prefix of (b), but (a \ne b); or in the first position where (a) and (b) differ, the sequence (a) has a smaller element than the corresponding element in (b). Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10)). The description of the test cases follows. Each test case consists of a single line with an integer (n) ((1 \le n \le 30)) — the number of vertices in the graph. The jury guarantees that the given graph does not contain cycles or multiple edges. Note that (m) is unknown to you! The interaction for each test case begins with reading the integer (n). Then you can ask up to (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, re