This is the Hard version of the problem. The difference between the versions is that in this version, you can make at most (30) queries. You can hack only if you solved all versions of this problem. This problem is interactive. There is a permutation(^{\text{∗}}) (p) of the integers from (0) to (n-1) hidden from you. Additionally, you are given (q) ranges (l_1, r_1, l_2, r_2, \ldots, l_q, r_q) where (1 \le l_i \le r_i \le n). You need to discover the maximum (\operatorname{MEX}) among the values of (p) in the (q) ranges that are given to you in the input. Formally, you must discover the value of (\max _{i=1}^q {\operatorname{MEX}(p_{l_i}, p_{l_i+1}, \ldots, p_{r_i})})(^{\text{†}}). To do this, you may make at most (30) queries of the following form: Choose any two integers (1 \le l \le r \le n) and you will receive the value (\operatorname{MEX}(p_{l}, p_{l+1}, \ldots, p_{r})). (^{\text{∗}})A permutation of the integers from (0) to (n-1) is a sequence of (n) elements where every integer from (0) to (n-1) appears exactly once. For example, the sequence (0, 3, 1, 2) is a permutation, but the sequence (0, 0, 2, 1) is not. (^{\text{†}})The (\operatorname{MEX}) of a sequence is defined as the smallest non-negative integer that does not appear in that sequence. For example, (\operatorname{MEX}(0, 0, 1, 3) = 2) and (\operatorname{MEX}(1, 2, 2) = 0.) Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 100)). The description of the test cases follows. The first line of each test case contains exactly two integers (n) and (q) ((4 \le n \le 10^4), (1 \le q \le 3 \cdot 10^5)) — the size of the permutation and the number of ranges, respectively. The (i)-th of the next (q) lines contains two integers (l_i, r_i) ((1 \le l_i \le r_i \le n)). It is guar