P1077长街行（street）

【题目背景】

船队带着沉没遗迹的抄本回到晨汐港。港口即将把这些记录送往内陆，长街上的住户也准备随队启程，Ehundategh 负责为他们安排同行队伍。

【题目描述】

长街的一侧共有 $n$ 户住户，依次编号为 $1\sim n$。第 $i$ 户持有一枚编号为正整数 $a_i$ 的通行牌。将 $a_i$ 写成二进制后，每个值为 $1$ 的位置都对应一种这户住户拥有的通行印记。

Ehundategh 共需要处理 $q$ 次安排。每次安排给出两个整数 $l,r$，他需要从编号在 $l\sim r$ 之间的住户中选择若干户，组成一支非空的同行队伍。同一户住户不能被重复选择，但通行牌编号相同的不同住户可以同时加入队伍。

长街的关卡会检查队伍是否拥有至少一种共同的通行印记。一支同行队伍能够顺利通过关卡，当且仅当队伍中所有通行牌编号按位与之后不为 $0$。

请你求出每次安排中，能够顺利通过长街的同行队伍最多包含多少户住户。

形式化题意：给定正整数序列 $a_1,a_2,\ldots,a_n$，对于每次询问 $[l,r]$，求

【输入格式】

从文件 $\textbf{\textit{street.in}}$ 中读入数据。

本题包含多组测试数据。

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

对于每组测试数据：

第一行包含两个正整数 $n,q$，表示住户数量与安排次数。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示每户住户的通行牌编号。

接下来 $q$ 行，每行包含两个正整数 $l,r$，表示一次安排涉及的住户编号区间。

【输出格式】

输出到文件 $\textbf{\textit{street.out}}$ 中。

对于每组测试数据输出 $q$ 行，每行一个整数，依次表示每次安排中同行队伍人数的最大值。

【样例 1 输入】

10 225 433 5 6 10 1241 552 463 374 586 391 2 4 8 7 3101 6112 5125 6

【样例 1 输出】

13223142536272

【说明/提示】

【样例 1 解释】

在第一组测试数据的第一次安排中，可以选择第 $1,3,5$ 户，三个整数按位与的结果为 $3\mathbin{\&}6\mathbin{\&}12=0$，因此这并不是一种合法选择。选择第 $2,3,5$ 户时，结果为 $5\mathbin{\&}6\mathbin{\&}12=4$，可以得到一支人数为 $3$ 的同行队伍。

【样例 2】

见选手目录下的 $\textbf{\textit{street/street2.in}}$ 和 $\textbf{\textit{street/street2.ans}}$。

该组样例符合测试点 $1\sim 3$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{street/street3.in}}$ 和 $\textbf{\textit{street/street3.ans}}$。

该组样例符合测试点 $4\sim 7$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{street/street4.in}}$ 和 $\textbf{\textit{street/street4.ans}}$。

该组样例符合测试点 $8\sim 15$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{street/street5.in}}$ 和 $\textbf{\textit{street/street5.ans}}$。

该组样例符合测试点 $16\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 20$，$1\leq n,q\leq 2\times 10^5$，$1\leq a_i\leq 10^9$，$1\leq l\leq r\leq n$。对于同一个测试点，保证 $\sum n\leq 2\times 10^5$，$\sum q\leq 2\times 10^5$。