C. Hidden Permutationstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis is an interactive problem.The jury has a permutation p of length n and wants you to guess it. For this, the jury created another permutation q of length n. Initially, q is an identity permutation (q_i = i for all i).You can ask queries to get q_i for any i you want. After each query, the jury will change q in the following way:   At first, the jury will create a new permutation q' of length n such that q'_i = q_{p_i} for all i.  Then the jury will replace permutation q with pemutation q'. You can make no more than 2n queries in order to quess p.InputThe first line of input contains a single integer t (1 \leq t \leq 1000) — the number of test cases.InteractionInteraction in each test case starts after reading the single integer n (1 \leq n \leq 10^4) — the length of permutations p and q.To get the value of q_i, output the query in the format ? i (1 \leq i \leq n). After that you will receive the value of q_i.You can make at most 2n queries. After the incorrect query you will receive 0 and you should exit immediately to get Wrong answer verdict.When you will be ready to determine p, output p in format ! p_1 p_2 \ldots p_n. After this you should go to the next test case or exit if it was the last test case. Printing the permutation is not counted as one of 2n queries.After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:  fflush(stdout) or cout.flush() in C++;  System.out.flush() in Java;  flush(output) in Pascal;  stdout.flush() in Python;  see documentation for other languages. It is guaranteed that the sum of n over all test cases doesn't exceed 10^4. The interactor is not adaptive in this problem.Hacks:To hack, use the following format:The first line contains the single integer t — the number of test cases.The first line of each test case contains the single integer n — the length of the permutations p and q. The second line of each test case contains n integers p_1, p_2, \ldots, p_n — the hidden permutation for this test case.ExampleInput
2
4

3

2

1

4

2

4

4Output
? 3

? 2

? 4

! 4 2 1 3

? 2

? 3

? 2

! 1 3 4 2NoteIn the first test case the hidden permutation p = [4, 2, 1, 3].Before the first query q = [1, 2, 3, 4] so answer for the query will be q_3 = 3.Before the second query q = [4, 2, 1, 3] so answer for the query will be q_2 = 2.Before the third query q = [3, 2, 4, 1] so answer for the query will be q_4 = 1.In the second test case the hidden permutation p = [1, 3, 4, 2].Empty strings are given only for better readability. There will be no empty lines in the testing system.
2
4

3

2

1

4

2

4

4
? 3  ? 2  ? 4  ! 4 2 1 3  ? 2  ? 3  ? 2  ! 1 3 4 2
['dfs and similar', 'interactive', 'math', '*1700']