对于一个长度为 n (n \geq 3) 的 01 串 S = s_1 \ldots s_n，定义变换 T = f(S) = t_1 \ldots t_n 如下：

i, & i \geq 3 \text{ 且 } s{i-2} = 0, \ s{i-1}, & i \geq 3 \text{ 且 } s{i-2} = 1. \end{cases}$$

定义变换 f 的 不动点 如下：若 01 串 T 满足 f(T) = T，则称 T 为变换 f 的不动点。

记 f^k(S) 为 S 经过 k 次变换得到的串。特别地，记 f^0(S) = S。求最小的自然数 k，使得 f^k(S) 为变换 f 的不动点，即满足 f^{k+1}(S) = f^k(S) 的最小的自然数 k。可以证明，一定存在自然数 k 使得 f^k(S) 为变换 f 的不动点。

小 Z 觉得这个问题过于简单，因此他增加了 q 次修改操作。第 i (1 \leq i \leq q) 次修改会给定两个正整数 l_i, r_i (1 \leq l_i \leq r_i \leq n)，然后将区间 [l_i, r_i] 内的所有原有的 0 替换为 1，所有原有的 1 替换为 0。你需要对初始时及每次修改后的字符串 S，求出最小的自然数 k，使得 f^k(S) 为变换 f 的不动点。

本题包含多组测试数据。

输入的第一行包含两个非负整数 c, t，分别表示测试点编号与测试数据组数。c = 0 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

第一行包含两个正整数 n, q，分别表示 S 的长度和修改次数。

第二行包含一个长度为 n 的 01 串 S = s_1 \ldots s_n，表示初始时的字符串。

第 i + 2 (1 \leq i \leq q) 行包含两个正整数 l_i, r_i，表示一次修改操作。

对于每组测试数据，设初始时的答案为 k_0，第 i (1 \leq i \leq q) 次修改后的答案为 $ki，输出一行一个正整数，表示 \oplus{i=0}^{q} ((i + 1) \times k_i)，其中 \oplus$ 表示 二进制按位异或。

该样例共包含两组测试数据。

对于第一组测试数据：

• 初始时，S = 11010，f(S) = 11100，f^2(S) = 11110，f^3(S) = f^4(S) = 11111，因此 k_0 = 3；
• 第一次操作后，S = 11110，f(S) = f^2(S) = 11111，因此 k_1 = 1；
• 第二次操作后，S = 10110，f(S) = f^2(S) = 10011，因此 k_2 = 1。

故答案为 \bigoplus_{i=0}^{q} ((i+1) \times k_i) = (1 \times 3) \oplus (2 \times 1) \oplus (3 \times 1) = 3 \oplus 2 \oplus 3 = 2。

对于第二组测试数据：

• 初始时，S = 1010100，k_0 = 1；
• 第一次操作后，S = 1010101，k_1 = 1；
• 第二次操作后，S = 1101101，k_2 = 5；
• 第三次操作后，S = 0001101，k_3 = 2。

故答案为 \bigoplus_{i=0}^{q} ((i+1) \times k_i) = (1 \times 1) \oplus (2 \times 1) \oplus (3 \times 5) \oplus (4 \times 2) = 4。

NOI