Keria 厌倦了辅助远程输出（ranged carries），现在他正在设计一道关于支持区间查询的数据结构题。

对于一个长度为 $m$ 且满足 $b_i = 0$ 或 $b_i = 1$ 的数组 $b = [b_1, b_2, \dots, b_m]$，考虑以下三元删除（triple removal）操作：

1. 选择三个下标 $1 \le i < j < k \le m$，使得这些位置上的元素相同（$b_i = b_j = b_k$）。
2. 从数组中删除这三个元素。该操作的代价定义为 $\min(k-j, j-i)$。删除后，数组的剩余部分将拼接在一起，并重新标记下标。

我们希望通过三元删除操作使数组 $b$ 变为空。因此，我们将一个数组的总代价定义为使该数组变为空所需的三元删除操作的最小可能代价和。如果无法使数组变为空，则代价定义为 $-1$。

Keria 想要测试他的数据结构。为此，你必须回答 $q$ 个独立的询问。最初，给你一个长度为 $n$ 的数组 $a = [a_1, a_2, \dots, a_n]$，其中 $a_i = 0$ 或 $a_i = 1$。对于每个询问，给你一个区间 $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$ ($a_i = 0$ 或 $a_i = 1$) —— 数组的元素。

接下来 $q$ 行。其中第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le n$) —— 第 $i$ 次询问的子数组区间。

保证所有测试用例中 $n$ 的总和不超过 $250\,000$。

保证所有测试用例中 $q$ 的总和不超过 $250\,000$。

输出格式

对于每个测试用例，输出 $q$ 行。第 $i$ 行应包含一个整数，表示第 $i$ 次询问的答案。

样例

输入 1

2
12 4
0 0 1 1 0 1 0 1 0 1 1 0
1 12
2 7
5 10
6 11
6 3
0 0 0 1 1 1
1 3
4 6
1 6

输出 1

4
2
3
-1
1
1
2

说明

第一个测试用例，第一次询问 (1 12) 的解释：

子数组为 $[0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0]$。其中有六个 $0$ 和六个 $1$。一种可能的最佳操作序列如下：

1. 删除下标为 $3, 4, 6$ 的三个 $1$。代价为 $\min(6 - 4, 4 - 3) = \min(2, 1) = 1$。数组变为 $[0, 0, 0, 0, 1, 0, 1, 1, 0]$。
2. 删除下标为 $1, 2, 3$ 的三个 $0$。代价为 $\min(3 - 2, 2 - 1) = \min(1, 1) = 1$。数组变为 $[0, 1, 0, 1, 1, 0]$。
3. 删除下标为 $2, 4, 5$ 的三个 $1$。代价为 $\min(5 - 4, 4 - 2) = \min(1, 2) = 1$。数组变为 $[0, 0, 0]$。
4. 删除下标为 $1, 2, 3$ 的三个 $0$。代价为 $\min(3 - 2, 2 - 1) = \min(1, 1) = 1$。数组现在为空。

总代价为 $1 + 1 + 1 + 1 = 4$。