A16670 | Diadrash (Easy Version)

这是该问题的简单版本。本版本与其他版本的区别在于，你最多可以进行 $ \max(300, \lceil\frac{n}{2}\rceil+2) $ 次查询。只有当你解决了所有版本后，才可以进行 Hack。

本题为交互式题目。

有一个长度为 $n$ 的排列 $p$（从 $0$ 到 $n-1$ 的一个排列）对你隐藏。同时，给定 $q$ 个区间 $[l_1, r_1], [l_2, r_2], \ldots, [l_q, r_q]$，其中 $1 \le l_i \le r_i \le n$。

你需要找出在输入给定的 $q$ 个区间中，$p$ 对应的子序列的最大 $\operatorname{MEX}$。形式化地，你需要找出 $ \max_{i=1}^q \{\operatorname{MEX}([p_{l_i}, p_{l_i+1}, \ldots, p_{r_i}])\} $ 的值。为此，你最多可以进行 $ \max(300, \lceil\frac{n}{2}\rceil+2) $ 次如下类型的询问：

- 任选任意两个整数 $1 \le l \le r \le n$，你会得到 $\operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])$ 的值。

$^*$ 长度为 $n$ 的排列是 $[0, 1, \ldots, n-1]$ 的一个重新排列，使得每个数仅出现一次。例如，序列 $[0, 3, 1, 2]$ 是一个排列，而 $[0, 0, 2, 1]$ 不是。

$^\dagger$ $\operatorname{MEX}$ 指的是序列中未出现的最小非负整数。例如，$\operatorname{MEX}([0, 0, 1, 3]) = 2$，$\operatorname{MEX}([1, 2, 2]) = 0$。

每组测试数据包含多组用例。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例组数。

每组测试数据的第一行包含两个整数 $n$ 和 $q$（$4 \le n \le 10^4$，$1 \le q \le 3 \times 10^5$），分别表示排列的长度和区间的数量。

接下来的 $q$ 行，每行包含两个整数 $l_i, r_i$（$1 \le l_i \le r_i \le n$）。

保证所有测试用例中 $n$ 之和不超过 $10^4$，$q$ 之和不超过 $3 \times 10^5$。

额外约束：同一组测试数据内没有重复的区间。