This is an interactive problem. This is the hard version of the problem. The only difference is the limit on the number of queries. You can make hacks only if all versions of the problem are solved. There is a hidden bracket sequence (s) of length (n), where (s) only contains ('(') and (')'). It is guaranteed that (s) contains at least one ('(') and one (')'). To find this bracket sequence, you can ask queries. Each query has the following form: you pick an integer (k) and arbitrary indices (i_1, i_2, \ldots, i_k) ((1 \le k \le 1000), (1 \le i_1, i_2, \ldots, i_k \le n)). Note that the indices can be equal. Next, you receive an integer (f(s_{i_1}s_{i_2}\ldots s_{i_k})) calculated by the jury. For a bracket sequence (t), (f(t)) is the number of non-empty regular bracket substrings in (t) (the substrings must be contiguous ). For example, (f("()())") = 3). A bracket sequence is called regular if it can be constructed in the following way. The empty sequence (\varnothing) is regular. If the bracket sequence (A) is regular, then (\mathtt{(}A\mathtt{)}) is also regular. If the bracket sequences (A) and (B) are regular, then the concatenated sequence (A B) is also regular. For example, the sequences ("(())()"), ("()") are regular, while ("(()") and ("())(") are not. Find the sequence (s) using no more than (100) queries. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 20)). The description of the test cases follows. The first line of each test case contains one integer (n) ((2 \le n \le 1000)). At this moment, the bracket sequence (s) is chosen. The interactor in this task is not adaptive . In other words, the bracket sequence (s) is fixed in every test case and does not change during th