This is an interactive problem. Kevin has (n) classmates, numbered (1, 2, \ldots, n). Any two of them may either be friends or not friends. Kevin wants to select (2k) classmates to form (k) teams, where each team contains exactly (2) people. Each person can belong to at most one team. Let (u_i) and (v_i) be two people in the (i)-th team. To avoid potential conflicts during team formation, the team members must satisfy one of the following two conditions: For all (i) ((1\leq i \leq k)), classmate (u_i) and (v_i) are friends. For all (i) ((1\leq i \leq k)), classmate (u_i) and (v_i) are not friends. Kevin wants to determine the maximum (k) such that, regardless of the friendship relationships among the (n) people, he can always find (2k) people to form the teams. After that, he needs to form (k) teams. But asking whether two classmates are friends is awkward, so Kevin wants to achieve this while asking about the friendship status of no more than (n) pairs of classmates. The interactor is adaptive . It means that the hidden relationship between classmates is not fixed before the interaction and will change during the interaction. 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 first line of each test case contains one positive integer (n) ((2\leq n \leq 10^5)) — the number of classmates. First, you should output an integer (k) ((1\leq k\leq \frac{n}2)) — the maximum number of teams you can form. You can make queries in the following way — print one line of the form (?\;u\;v) where (1\leq u\neq v \leq n). After that, read a single integer: (0) or (1) indicating whether they are friends. (1) means they are friends while (0) means not. If you want to print the answer, output (!\;u_1\;v_1\;u_2\;v_2\;\ldots\;u_k\;v_k).