Bitwise Subsegment Exclusion

Input

The first line contains a single integer $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — the number of test cases.

The first line of each test case contains two integers $n$ and $q$ ( $1 \leq n, q \leq 2 \cdot 1 0^{5}$ 1 \le n, q \le 2 \cdot 10^5) — the length of the binary array and the number of queries.

The second line of each test case contains $n$ space-separated integers $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n ( $a_{i} \in {0, 1}$ a_i \in \{0, 1\}) — the elements of the array.

The next $q$ lines describe the queries. Each line contains two integers $l$ and $r$ ( $1 \leq l \leq r \leq n$ 1 \le l \le r \le n) — the boundaries of the query range.

It is guaranteed that both the sum of $n$ and the sum of $q$ over all test cases do not exceed $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Output

For each query, output a single integer on a new line — the minimum numerical value of a binary sequence that does not appear as a contiguous subsegment in $a [l \dots r]$ a[l \dots r], modulo $998244353$ .

Examples

Example 1

Loading

Note

In the first test case, the array is $a = [0, 1, 0]$ a = [0, 1, 0].

In the first query $[1, 3]$ , the contiguous subsegments present are $[0], [1], [0, 1], [1, 0]$ [0], [1], [0, 1], [1, 0], and $[0, 1, 0]$ [0, 1, 0]. Their respective decimal values are $2, 3, 5, 6,$ 2, 3, 5, 6, and $10$ . The smallest value that is not formed is $4$ , which corresponds to the sequence $[0, 0]$ .
In the second query $[1, 2]$ , the subarray is $[0, 1]$ . The subsegments present are $[0], [1],$ [0], [1], and $[0, 1]$ . The smallest missing value is again $4$ (sequence $[0, 0]$ ).
In the third query $[2, 2]$ , the subarray is $[1]$ . The only subsegment present is $[1]$ (value $3$ ). The smallest missing value is $2$ (sequence $[0]$ ).

In the second test case, the array is $a = [1, 1, 1, 1]$ a = [1, 1, 1, 1]. For the query $[1, 4]$ , the sequence $[0]$ (value $2$ ) never appears, so the answer is $2$ .

In the third test case, the array is $a = [1, 0, 0, 1]$ a = [1, 0, 0, 1].

For the query $[1, 3]$ , the subarray is $[1, 0, 0]$ [1, 0, 0]. It contains $[0], [1], [0, 0], [1, 0]$ [0], [1], [0, 0], [1, 0] (values $2, 3, 4, 6$ 2, 3, 4, 6). The smallest missing value is $5$ (sequence $[0, 1]$ ).
For the query $[2, 4]$ , the subarray is $[0, 0, 1]$ [0, 0, 1]. It contains $[0], [1], [0, 0], [0, 1]$ [0], [1], [0, 0], [0, 1] (values $2, 3, 4, 5$ 2, 3, 4, 5). The smallest missing value is $6$ (sequence $[1, 0]$ ).
For the query $[1, 4]$ , the subarray contains values $2, 3, 4, 5,$ 2, 3, 4, 5, and $6$ . The smallest missing value is $7$ (sequence $[1, 1]$ ).

Scoring

Subtask 1 (100 points): $\sum n \leq 2000$ \sum n \le 2000 and $\sum q \leq 2000$ \sum q \le 2000.
Subtask 2 (150 points): $\sum n \leq 40000$ \sum n \le 40000 and $\sum q \leq 40000$ \sum q \le 40000.
Subtask 3 (250 points): No additional constraints.