水母序列

【题目描述】

Kano 是 Mahiru 的好朋友。在情人节，Kano 送给了 Mahiru 一个长度为 $n$ 的序列 $a_1,a_2,⋯,a_n$。

Mahiru 认为，一段序列是“水母的”，当且仅当其所有元素的按位或值在十进制表示下为质数。

例如，序列 $\{1,4,3\}$ 是“水母的”，因为 $1\ \mathrm{or}\ 4\ \mathrm{or}\ 3=7$ 为质数；但序列 $\{1,3,13\}$ 不是“水母的”，因为 $1\ \mathrm{or}\ 3\ \mathrm{or}\ 13=15$ 不为质数。

现在对于 Kano 送的这段序列，Mahiru 提出了 $m$ 个问题。每个问题形如 $l,r$，求序列 ${a_l,a_{l+1},⋯,a_r}$ 中有多少非空连续子序列是“水母的”。

注：$0$ 和 $1$ 均不是质数。

【输入格式】

第一行两个整数 $n,m$。

第二行包含了 $n$ 个非负整数 $a_1,a_2,⋯,a_n$，表示这个序列。

接下来 $m$ 行，每行包含两个正整数 $l,r$，表示一个问题。

【输出格式】

输出一共 $m$ 行，每行一个非负整数，表示对应问题的答案。

【样例输入】

4 4
1 4 2 5
1 4
2 3
2 4
3 3

【样例输出】

7
1
4
1

【数据规模与约定】

大样例

对于 $100\%$ 的数据 $1 \le n\le 10^5,1 \le m\le 10^6,0\le a_i\lt 2^{20}$。

·$Subtask1(40pts): n\le 1000$。

·$Subtask2(20pts): a_i\lt 16$。

·$Subtask3(20pts): n\le 5\times 10^4$。

·$Subtask4(20pts): 无特殊限制$。

温馨提示：我们不对 $m$ 的范围作特殊限制。

温馨提示：本题的IO量较大，请使用较快的IO方式。

【来源】

在此键入。