D. Bit Walk
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Habbab thinks that this problem is very easy, so are you going to be '3rrar' and run away from us without solving it, or 'lesa al-amana momkenah'?

You are given a binary array $$$a$$$ of length $$$n$$$, and $$$q$$$ queries. Each query provides a range $$$[l, r]$$$, corresponding to the subarray $$$b = a_l, a_{l+1}, \dots, a_r$$$ of length $$$m = r - l + 1$$$.

For each query, calculate the number of good cyclic shifts$$$^\dagger$$$ of $$$b$$$.

A binary array $$$c$$$ of length $$$m$$$ is considered good if the following process finishes with $$$x = 0$$$:

  • Initially, set $$$x = 0$$$ and $$$i = 1$$$.
  • If $$$c_i = 1$$$, replace $$$x$$$ by $$$1 - x$$$ and set $$$i := i + 1$$$.
  • If $$$c_i = 0$$$, leave $$$x$$$ unchanged and set $$$i := i + 2$$$.
  • The process stops when $$$i \gt m$$$.

$$$^\dagger$$$ A cyclic shift of $$$b$$$ is formed by moving its first $$$k$$$ elements to the end ($$$0 \le k \lt m$$$), resulting in the array $$$b_{k+1}, \dots, b_m, b_1, \dots, b_k$$$. All $$$m$$$ possible shifts are counted independently for each query, even if they result in identical arrays.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case begins with a line containing two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the length of the array and the number of queries.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 1$$$).

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$), describing a query.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$, and the sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For every query, print one integer — the number of good cyclic shifts of the subarray in that query.

Example
Input
2
5 4
1 0 1 0 1
1 5
2 4
1 1
4 5
6 4
0 0 0 1 1 0
1 6
1 3
4 5
3 6
Output
2
1
0
1
4
3
2
3
Note

Consider the first test case.

  • For the subarray $$$[1, 0, 1, 0, 1]$$$, there are two good cyclic shifts:
    • For $$$k=2$$$, the shifted array is $$$[\underline{1}, \underline{0}, 1, \underline{1}, \underline{0}]$$$. The process visits these indices, where the values are $$$1, 0, 1, 0$$$. Since $$$x$$$ is flipped at indices corresponding to $$$1$$$ and $$$1$$$, $$$x$$$ finishes at $$$0$$$.
    • For $$$k=4$$$, the shifted array is $$$[\underline{1}, \underline{1}, \underline{0}, 1, \underline{0}]$$$. The process visits these indices, where the values are $$$1, 1, 0, 0$$$. $$$x$$$ is flipped at indices corresponding to $$$1$$$ and $$$1$$$, finishing at $$$x=0$$$.
    The other three shifts finish with $$$x=1$$$, so the answer for this query is $$$2$$$.
  • For the subarray $$$[1]$$$, the process visits the array as $$$[\underline{1}]$$$. The process flips $$$x$$$ once, so it is not good. The answer is $$$0$$$.
  • For the subarray $$$[1, 1]$$$, the shifts by $$$k=0$$$ and $$$k=1$$$ both result in the array $$$[\underline{1}, \underline{1}]$$$:
    • For both, the process visits the array as $$$[\underline{1}, \underline{1}]$$$. $$$x$$$ is flipped twice, so it is good.
    Both are counted separately, and the answer is $$$2$$$.