追逐专利
时间限制： 1 秒
内存限制： 512 MB
输入： 标准输入
输出： 标准输出
在猞猁的家中藏着一份关于动物城新区规划的专利——一份可能颠覆整个城市的文件。朱迪·霍普斯和尼克·王尔德得知专利放在其中一个家用保险箱里，但为了以防万一，猞猁将线索分散在 $n$ 个保险箱组成的链条上：第 $i$ 个保险箱上写有数字 $a_i$。要打开保险箱，需要一把齿数为 $d$ 的钥匙：只有当 $a_i$ 和 $d$ 互质（即除了 $1$ 以外没有公共因子）时，保险箱才能打开。
朱迪和尼克计划检查连续的一组保险箱——共有 $q$ 个询问，每个询问给出区间 $[l, r]$。对于每个区间，他们想要制作一把万能钥匙，使得齿数 $d$ 尽可能小，并且这把钥匙能打开区间内的所有保险箱。已知 $d$ 必须是整数且不小于 $2$。
请帮助角色们解决这个问题，并给出每个询问的最小 $d$！
输入数据
第一行包含两个整数 $n, q$ —— 保险箱的数量和询问的数量（$1 \le n, q \le 2 \cdot 10^5$）。
第二行包含 $n$ 个整数 $a_i$ —— 保险箱上的数字（$1 \le a_i \le 10^7$）。
接下来 $q$ 行，每行包含两个整数 $l, r$ —— 询问的区间（$1 \le l \le r \le n$）。
输出数据
对于每个询问，输出一行答案。
评分系统
| 子任务 | 分数 | 额外限制 | 所需子任务 | 验证信息 |
|---|---|---|---|---|
| 0 | – | 样例 | 无 | 完全 |
| 1 | 5 | $n, q \le 50; \, a_i \le 100$ | 无 | 首次错误 |
| 2 | 8 | $n, q \le 2000; \, a_i \le 500$ | 1 | 首次错误 |
| 3 | 7 | $a_i \le 3$ | 无 | 首次错误 |
| 4 | 7 | 所有询问 $l = r$；$a_i \le 10^5$ | 无 | 首次错误 |
| 5 | 8 | 所有询问 $l = r$ | 4 | 首次错误 |
| 6 | 10 | 所有 $a_i$ 均为素数 | 无 | 首次错误 |
| 7 | 10 | $n, q \le 2 \cdot 10^4$ | 1, 2 | 首次错误 |
| 8 | 15 | $n \le 10^5; \, q \le 2 \cdot 10^4$ | 1, 2, 7 | 首次错误 |
| 9 | 10 | $n, q \le 8 \cdot 10^4$ | 1, 2, 7, 8 | 首次错误 |
| 10 | 20 | 无 | 0–9 | 首次错误 |
样例
样例 #1
输入
6 5
6 10 15 7 9 14
1 3
2 5
4 4
5 6
1 6输出
7
11
2
5
11样例 #2
输入
5 5
2 3 6 10 15
1 1
2 2
1 3
3 5
1 5输出
3
2
5
7
7