题目背景

你正在追番，突然家长进来了，于是你假装在写一道数据结构题。

题目描述

定义一个长度为 $m$ 的数组 $v$ 是合法的，当且仅当经过若干次以下操作可以使 $v$ 中的所有元素相等：

• 选择四个整数 $a,b,c,d$（$1\leq a\leq b\leq m$，$1\leq c\leq d\leq m$）满足 $b-a+1=d-c+1$，且 $v_a\operatorname{~or~}v_{a+1}\operatorname{~or~}\cdots\operatorname{~or~}v_b=v_c\operatorname{~or~}v_{c+1}\operatorname{~or~}\cdots\operatorname{~or~}v_d$，其中 $\operatorname{or}$ 表示按位或运算。接下来，将区间 $[a,b]$ 的数复制下来再覆盖到区间 $[c,d]$。注意：区间 $\bm{[a,b]}$ 和 $\bm{[c,d]}$ 可能会相交。

给出一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$ 以及 $q$ 次询问，每次询问给定两个正整数 $l,r$，你需要回答区间 $[l,r]$ 内的最长合法子区间的长度。

输入格式

从标准输入读入数据。

本题含有多组测试数据。

输入的第一行包含两个整数 $T,id$，表示数据组数和测试点编号（样例的测试点编号为 $0$）。

对于每组测试数据数据，第一行两个正整数 $n,q$，表示序列长度与询问次数。

第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示序列 $a$ 中每个元素的值。

接下来 $q$ 行，每行两个正整数 $l,r$，表示询问的区间。

输出格式

输出到标准输出。

对于每组测试数据的每次询问，输出一行一个整数，表示区间 $[l,r]$ 内的最长合法子区间的长度。

2 0
7 2
0 4 2 6 0 6 6
1 7
2 3
3 1
1 2 3
1 3

7
1
3

提示

【样例解释 #1】

对于第一组数据的第一个询问，最长的合法子区间为 $[1,7]$，以下是一种可能的操作序列：

1. 选择区间 $[1,4]$ 和 $[2,5]$，将区间 $[1,4]$ 中的数先复制下来，再覆盖到 $[2,5]$ 上，此时序列变为 $[0,0,4,2,6,6,6]$。

2. 选择区间 $[5,6]$ 和 $[3,4]$，此时序列变为 $[0,0,6,6,6,6,6]$。

3. 选择区间 $[4,7]$ 和 $[1,4]$，此时序列变为 $[6,6,6,6,6,6,6]$。

注意，操作并不会真正的修改原序列中的值。

对于第一组数据的第二个询问，最长的合法子区间为 $[2,2]$ 和 $[3,3]$。

【样例 #2】

见选手目录下的 binary/binary2.in 与 binary/binary2.ans。

这个样例满足测试点 $5\sim 8$ 的条件限制。

【样例 #3】

见选手目录下的 binary/binary3.in 与 binary/binary3.ans。

这个样例满足测试点 $25\sim 31$ 的条件限制。

【样例 #4】

见选手目录下的 binary/binary4.in 与 binary/binary4.ans。

这个样例满足测试点 $46\sim 50$ 的条件限制。

---

【数据范围】

对于所有数据保证：$1\le T\le 2\times 10^5$，$1\le n,q,\sum n,\sum q\le 2\times 10^6$，$0\le a_i < 2^{30}$。

测试点编号	$\sum n\le$	$\sum q\le$	特殊性质
$1$	$5$		无
$2\sim 4$	$100$
$5\sim 8$	$1000$	$1000$
$9\sim 14$		$10^6$
$15\sim 19$	$6000$
$20\sim 24$	$50000$	$10$
$25\sim 31$	$10^5$		B
$32\sim 36$	$2\times 10^5$		无
$37\sim 41$	$5\times 10^5$	$10^6$	B
$42\sim 44$		$5\times 10^5$	无
$45$	$2\times 10^6$		A
$46\sim 50$			无

• 特殊性质 A：保证序列 $a$ 中的每个数均在 $[0,2^{30})$ 之间均匀随机生成。
• 特殊性质 B：保证对于任意 $1\le i\le n$，$a_i\le 3$。

---

【提示】

本题输入输出量较大，请使用适当的 I/O 方式。

请注意常数因子对程序运行效率产生的影响。

KDOI 出题组温馨提示：多测不清空，爆零两行泪。