This is the hard version of the problem. The difference between the versions is that in this version, (n \leq 400) and you may make (1500) queries. You can hack only if you solved all versions of this problem. This is an interactive problem. Let (n) be a positive integer. A function on (n) variables (x_1, \ldots, x_n) is called min-max if it can be constructed as writing only (\min) and (\max) calls around (x_1, \ldots, x_n) with each variable appearing exactly once in order from left to right in the expression. For example, (\min(x_1, x_2, x_3)) is a min-max function on (3) variables, but (\max(\min(x_1, x_3), x_2)) and (\min(\max(x_1, x_2), \max(x_2, x_3))) are not. Bowser has chosen a min-max function on (n) ((2 \leq n \leq 400)) variables and tells you (n). Additionally, he lets you ask queries of the following form: you give Bowser (n) integers (x_1, \ldots, x_n) ((1 \leq x_i \leq 10^9)) as input, and he tells you (f(x_1, \ldots, x_n)). To escape his castle, you have to deduce his function using at most (1500) queries in total. After that, to prove to him that you have learned the function, Bowser will give you up to (5000) of his own inputs (x_1, \ldots, x_n), to which you must respond with the correct value of (f(x_1, \ldots, x_n)). Since Bowser's castle is very secure, he actually has multiple functions for you to figure out, with a total variable count of at most (400). Additionally, he constrains that you use at most (1500) queries across all of the functions and that he will also not ask more than (5000) queries in total. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 200)). The description of the test cases follows. The first line of each test case contains a single integer (n) ((2 \leq n \leq 400)) — the number of variables in the min-max function. It is guaranteed t