Given a binary string $S = s_1 \dots s_n$ of length $n$ $(n \ge 3)$, define the transformation $T = f(S) = t_1 \dots t_n$ as follows:

$t_i = \begin{cases} s_i, & i \le 2, \\ s_i, & i \ge 3 ~ \text{and} ~ s_{i - 2} = 0, \\ s_{i - 1}, & i \ge 3 ~ \text{and} ~ s_{i - 2} = 1. \end{cases}$

A fixed point of the transformation $f$ is defined as follows: if a binary string $T$ satisfies $f(T) = T$, then $T$ is called a fixed point of the transformation $f$.

Let $f^k(S)$ denote the string obtained after applying the transformation $k$ times to $S$. Specifically, define $f^0(S) = S$. Find the smallest natural number $k$ such that $f^k(S)$ is a fixed point of $f$, i.e., the minimal natural number $k$ such that $f^{k+1}(S) = f^k(S)$. It can be proved that there always exists a natural number $k$ such that $f^k(S)$ is a fixed point of $f$.

Little Z thinks this problem is too easy, so he added $q$ modification operations. In the $i$-th $(1 \le i \le q)$ modification, you are given two positive integers $l_i, r_i$ $(1 \le l_i \le r_i \le n)$, and you flip all the bits in the interval $[l_i, r_i]$ (i.e., change all $0$s to $1$s and all $1$s to $0$s). For the initial string $S$ and after each modification, you need to compute the smallest natural number $k$ such that $f^k(S)$ is a fixed point of $f$.

Input Format

Read from standard input.

This problem contains multiple test cases.

The first line contains two non-negative integers $c, t$, representing the test point number and the number of test cases, respectively. $c = 0$ means the test point is a sample.

For each test case, input is as follows:

The first line contains two positive integers $n, q$, representing the length of $S$ and the number of modifications.

The second line contains a binary string $S = s_1 \dots s_n$ of length $n$, representing the initial string.

For each $i$ $(1 \le i \le q)$, the $(i+2)$-th line contains two positive integers $l_i, r_i$, representing a modification operation.

Output Format

Output to standard output.

For each test case, let $k_0$ be the answer for the initial string, and $k_i$ be the answer after the $i$-th modification $(1 \le i \le q)$. Output a single line containing one positive integer, representing $\bigoplus_{i = 0} ^ q \left((i + 1) \times k_i\right)$, where $\oplus$ denotes the bitwise XOR operation.

Sample

Input

0 2
5 2
11010
3 3
2 2
7 3
1010100
7 7
2 4
1 2

Output

2
4

Explanation

There are two test cases in this sample.

For the first test case:

• Initially, $S = 11010$, $f(S) = 11100$, $f^2(S) = 11110$, $f^3(S) = f^4(S) = 11111$, so $k_0 = 3$;
• After the first operation, $S = 11110$, $f(S) = f^2(S) = 11111$, so $k_1 = 1$;
• After the second operation, $S = 10110$, $f(S) = f^2(S) = 10011$, so $k_2 = 1$.

Therefore, the answer is $\bigoplus_{i = 0} ^ q \left((i + 1) \times k_i\right) = (1 \times 3) \oplus (2 \times 1) \oplus (3 \times 1) = 3 \oplus 2 \oplus 3 = 2$.

For the second test case:

• Initially, $S = 1010100$, $k_0 = 1$;
• After the first operation, $S = 1010101$, $k_1 = 1$;
• After the second operation, $S = 1101101$, $k_2 = 5$;
• After the third operation, $S = 0001101$, $k_3 = 2$.

Therefore, the answer is $\bigoplus_{i = 0} ^ q \left((i + 1) \times k_i\right) = (1 \times 1) \oplus (2 \times 1) \oplus (3 \times 5) \oplus (4 \times 2) = 4$.

Second Sample

See ex_2.in and ex_2.ans in the download directory.

This sample satisfies the constraints of test points $1 \sim 3$.

Third Sample

See ex_3.in and ex_3.ans in the download directory.

This sample satisfies the constraints of test points $4 \sim 6$.

Fourth Sample

See ex_4.in and ex_4.ans in the download directory.

This sample satisfies the constraints of test points $13, 14$.

Fifth Sample

See ex_5.in and ex_5.ans in the download directory.

This sample satisfies the constraints of test points $17 \sim 19$.

Data Range

Let $N, Q$ be the sums of $n$ and $q$ over all test cases within a single test point. For all test cases, it is guaranteed that:

• $1 \le t \le 5$;
• $3 \le n \le 4 \times 10^{5}$, $N \le 8 \times 10^{5}$;
• $1 \le q \le 4 \times 10^{5}$, $Q \le 8 \times 10^{5}$;
• For all $1 \le i \le n$, $s_i \in {0, 1}$;
• For all $1 \le i \le q$, $1 \le l_i \le r_i \le n$.

Special Property A: It is guaranteed that for the initial string and after each modification, there exists an integer $p \in \[2, n]$ such that $s_1 = s_2 = \dots = s_p = 1$ and $s_{p + 1} = \dots = s_n = 0$.

Special Property B: It is guaranteed that for all $1 \le i \le q$, $l_i = 1$, $r_i = n$.

Special Property C: It is guaranteed that for all $1 \le i \le q$, $l_i = 1$, and $r_1 \le r_2 \le \dots \le r_q$.