暂无测试数据。

给定一个长度为 $N$ 的序列 $A$，有 $Q$ 次询问。

每次询问给定一个区间 $[l,r]$，记 $m$ 为 $A_l,A_{l+1},A_{l+2},…,A_r$ 中的最大值，请统计 $A_l,A_{l+1},A_{l+2},…,A_r$ 中有多少数和 $m$ 互质。

注：如果 $a, b$ 互质，则 $a, b$ 的最大公约数为 $1$。

输入格式

第一行两个正整数 $N,Q$。

第二行 $N$ 个正整数，表示序列 $A$。

接下来 $Q$ 行，每行两个正整数 $l,r$ 表示一个询问。

输出格式

输出 $Q$ 行，每行一个非负整数，依次回答每个询问。

数据范围

对于 $20\%$ 的数据，有 $1\leq N,Q \leq 10^3$。

对于另外 $20\%$ 的数据，有 $1\leq A_i \le 2$。

对于所有数据，有 $1 \le N,Q \le 10^5; 1 \le A_i \le 20,1 \le l \le r \le N$。

6 3
1 2 3 4 2 4
1 4
1 3
4 6

2
2
0