Description: This is an interactive problem. You are given an integer $$$n$$$. The jury has hidden from you a directed graph with $$$n$$$ vertices (numbered from $$$1$$$ to $$$n$$$) and some number of edges. You additionally know that: - The graph only contains edges of the form $$$i \leftarrow j$$$, where $$$1 \le i < j \le n$$$. - For any three vertices $$$1 \le i < j < k \le n$$$, at least one of the following holds$$$^\dagger$$$: Vertex $$$i$$$ is reachable from vertex $$$j$$$, or Vertex $$$i$$$ is reachable from vertex $$$k$$$, or Vertex $$$j$$$ is reachable from vertex $$$k$$$. You want to color each vertex in either black or white such that for any two vertices $$$i$$$ and $$$j$$$ ($$$1 \le i < j \le n$$$) of the same color, vertex $$$i$$$ is reachable from vertex $$$j$$$. To do that, you can ask queries of the following type: - ? i j — is vertex $$$i$$$ reachable from vertex $$$j$$$ ($$$1 \le i < j \le n$$$)? Find any valid vertex coloring of the hidden graph in at most $$$2 \cdot n$$$ queries. It can be proven that such a coloring always exists. Note that the grader is not adaptive: the graph is fixed before any queries are made. $$$^\dagger$$$ Vertex $$$a$$$ is reachable from vertex $$$b$$$ if there exists a path from vertex $$$b$$$ to vertex $$$a$$$ in the graph. Input Format: Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of the test cases follows. The only line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 100$$$) — the number of vertices in the hidden graph. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$. Output Format: None Note: The hidden graph in the first test case: The hidden graph in the second test case: The interaction happens as follows: SolutionJuryExplanation2There are $$$2$$$ test cases.4In the first test case, the graph has $$$4$$$ vertices.? 1 2 YESThe solution asks if vertex $$$1$$$ is reachable from vertex $$$2$$$, and the jury answers YES.? 2 3 YESThe solution asks if vertex $$$2$$$ is reachable from vertex $$$3$$$, and the jury answers YES.? 1 3 YESThe solution asks if vertex $$$1$$$ is reachable from vertex $$$3$$$, and the jury answers YES.? 1 4 NOThe solution asks if vertex $$$1$$$ is reachable from vertex $$$4$$$, and the jury answers NO.? 2 4 NOThe solution asks if vertex $$$2$$$ is reachable from vertex $$$4$$$, and the jury answers NO.? 3 4 NOThe solution asks if vertex $$$3$$$ is reachable from vertex $$$4$$$, and the jury answers NO.! 0 0 0 1The solution has somehow determined a valid coloring and outputs it. Since the output is correct, the jury continues to the next test case.5In the second test case, the graph has $$$5$$$ vertices.! 1 1 0 1 0The solution has somehow determined a valid coloring, and outputs it. Since the output is correct and there are no more test cases, the jury and the solution exit. Note that the line breaks in the example input and output are for the sake of clarity, and do not occur in the real interaction.