This is the hard version of the problem. The difference between the versions is that in this version, you can make at most (10\cdot n) queries. You can hack only if you solved all versions of this problem. Ali loved Bahamin's gift (from problem E) so much that he illegally traveled from Qazvin to Liverpool to have the gift signed by football players. Now Interpol is searching for him, but they've offered a deal: solve a problem, and he can stay in Liverpool. But since he's currently at the stadium, he can't solve it — so he asked you to do it. This is an interactive problem. There is a hidden permutation(^{\text{∗}}) (p) of length (n\ge 4), where (p_i \neq i) for each (1 \leq i \leq n). Initially, you should give the jury a positive integer (k\le n), which will be constant through future queries. Then you need to find permutation (p) using some queries. In each query, you give a permutation (q_1, q_2, \ldots, q_n) to the jury. In response, you will receive the number of pairs ((i, j)) such that all of the following conditions hold: (i \lt j); (p_{q_i} = q_j); (i \neq k). ((k) is the constant you have given to the jury) You are given (n), and you need to find the permutation (p) in at most (10\cdot n) queries. (^{\text{∗}})A permutation of length (n) is an array consisting of (n) distinct integers from (1) to (n) in arbitrary order. For example, (2,3,1,5,4) is a permutation, but (1,2,2) is not a permutation ((2) appears twice in the array), and (1,3,4) is also not a permutation ((n=3) but there is (4) in the array). Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 500)). The description of the test cases follows. The only line of each test case contains a single integer (n) ((4 \leq n \leq 100)) — the length of (p). It is guaranteed that the sum of (n^2) over a