对于一个长度为 $m$ 的数组 $b = [b_1, b_2, \dots, b_m]$（$b_i \ge 2$），考虑以下由 Poby 和 Rekkles 进行的双人游戏。
- 玩家轮流进行操作，Poby 先手。
- 在 Poby 的回合，他必须选择一个元素 $x \ge 2$ 并将其替换为 $\lfloor \frac{x}{2} \rfloor$。换句话说，他选择一个满足 $b_i \ge 2$ 的下标 $i$（$1 \le i \le m$），然后执行 $b_i := \lfloor \frac{b_i}{2} \rfloor$。
- 在 Rekkles 的回合，他必须从数组 $b$ 中选择一个元素 $x \ge 2$ 并将其替换为 $x + 1$。换句话说，他选择一个满足 $b_i \ge 2$ 的下标 $i$（$1 \le i \le m$），然后执行 $b_i := b_i + 1$。
游戏在数组 $b$ 中的所有元素都等于 $1$ 时结束。
定义游戏的得分为 Poby 进行的操作次数。Poby 的目标是最小化得分，而 Rekkles 的目标是最大化得分。
那么，数组 $b$ 的值（value）即为双方均采取最优策略时游戏的得分。
给你一个长度为 $n$ 的整数数组 $a$（$a_i \ge 2$）。
回答 $q$ 个独立的查询。在每个查询中，给你一个区间 $1 \le l \le r \le n$，你必须求出数组 $[a_l, a_{l+1}, \dots, a_r]$ 的值。
输入格式
每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。
接下来是测试用例的描述。
每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 250\,000$）—— 数组的长度和查询的数量。
下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$2 \le a_i \le 10^9$）—— 数组 $a$ 的元素。
接下来 $q$ 行，其中第 $j$ 行包含两个整数 $l_j$ 和 $r_j$（$1 \le l_j \le r_j \le n$）—— 第 $j$ 次查询的子数组区间。
保证所有测试用例中 $n$ 的总和不超过 $250\,000$。
保证所有测试用例中 $q$ 的总和不超过 $250\,000$。
输出格式
对于每个测试用例，输出 $q$ 行。第 $i$ 行应该包含一个整数，表示第 $i$ 次查询的答案。
样例
输入样例 1
2 5 5 4 3 2 5 6 1 1 1 2 2 4 3 5 1 5 10 1 314 159 265 358 979 323 846 264 338 327 1 10
输出样例 1
2 3 5 6 10 91
说明
第一个测试用例，第一次查询（1 1）的解释：
子数组为 $[4]$。
- Poby: $4 \to \lfloor \frac{4}{2} \rfloor = 2$。数组变为 $[2]$。
- Rekkles: $2 \to 3$。数组变为 $[3]$。
- Poby: $3 \to \lfloor \frac{3}{2} \rfloor = 1$。数组变为 $[1]$，游戏结束。
可以证明该策略对双方都是最优的。因此，数组 $[4]$ 的值为 $2$。
第一个测试用例，第二次查询（1 2）的解释：
子数组为 $[4, 3]$。
- Poby: $3 \to \lfloor \frac{3}{2} \rfloor = 1$。数组变为 $[4, 1]$。
- Rekkles: $4 \to 5$。数组变为 $[5, 1]$。
- Poby: $5 \to \lfloor \frac{5}{2} \rfloor = 2$。数组变为 $[2, 1]$。
- Rekkles: $2 \to 3$。数组变为 $[3, 1]$。
- Poby: $3 \to \lfloor \frac{3}{2} \rfloor = 1$。数组变为 $[1, 1]$，游戏结束。
可以证明该策略对双方都是最优的。因此，数组 $[4, 3]$ 的值为 $3$。