给定一个长度为 $m$ 的数组 $A = (a_1, a_2, \dots, a_m)$，记 $B(A)$ 为对数组 $A$ 进行一轮冒泡排序后的结果，即对数组 $A$ 执行以下算法后的输出。

冒泡排序的一轮迭代

你可以对数组 $A = (a_1, a_2, \dots, a_m)$ 执行任意次（包括零次）以下操作：

• 选择一个区间 $[i, j]$，其中 $1 \le i \le j \le m$，并将元素 $a_i, a_{i+1}, \dots, a_{j-1}, a_j$ 向任一方向循环移位，使其变为 $a_j, a_i, a_{i+1}, \dots, a_{j-1}$ 或 $a_{i+1}, \dots, a_{j-1}, a_j, a_i$。

例如，如果我们对数组 $A = [1, 2, 3, 4, 5]$ 的区间 $[1, 4]$ 向右循环移位，得到的数组为 $A' = [4, 1, 2, 3, 5]$。

现在给定一个长度为 $n$ 的排列 $P = (p_1, p_2, \dots, p_n)$，你需要回答 $q$ 个独立的查询，形式如下：

• 在第 $i$ 个查询中，给定参数 $1 \le l_i \le r_i \le n$，你需要求出将子数组 $P[l_i, r_i]$ 变换为 $B(P[l_i, r_i])$ 所需的最少操作次数，其中 $P[l_i, r_i] = (p_{l_i}, p_{l_i+1}, \dots, p_{r_i})$。

输入格式

第一行包含一个整数 $T(1 \le T \le 10)$，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n, q(1 \le n, q \le 10^5)$，分别表示排列 $P$ 的长度和查询次数。

第二行包含 $n$ 个不同的整数 $p_1, p_2, \dots, p_n(1 \le p_i \le n)$。

接下来的 $q$ 行，每行包含两个整数 $l_i, r_i(1 \le l_i \le r_i \le n)$，表示第 $i$ 个查询的参数。

输出格式

对于每个测试用例中的每个查询，输出一行一个整数，表示答案。

样例

输入 1

1
10 5
3 7 9 2 6 4 5 8 10 1
1 10
2 6
7 9
4 9
3 3

输出 1

2
1
0
1
0

说明

对于样例中的第二个查询，我们可以通过对区间 $[2, 5]$（对应 $P$ 中的区间 $[3, 6]$）进行一次向左循环移位，将 $P[2, 6]$ 变换为 $B(P[2, 6])$：

$[7, 9, 2, 6, 4] \to [7, 2, 6, 4, 9]$。