E-「LAOI-15」ナイト・オブ・ナイツ

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$ ，定义一次操作为：任选一个元素 $a_i$ ，将 $a_i$ 除以它的一个质因子。
$\hspace{15pt}$ 你将要回答 $q$ 次询问，每次询问给定 $l,r$ ，求最小操作次数，使得对于任意的 $i\in[l,r)$ ，均有 $\gcd(a_i,a_{i+1})=1$ 。
$\hspace{15pt}$ 注意，操作不实际进行，即每次询问独立。

输入描述:

第一行输入两个正整数 ，表示序列长度、询问次数。
第二行输入  个整数 ，表示序列中的元素。
此后  行，第  行输入两个正整数 ，表示第  次询问的区间。

输出描述:

对于每次询问，新起一行输出一个整数，表示对应询问的答案。

示例1

输入

复制

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

输出

复制

1
1
2

说明

在这个样例中：
对于第一次询问，其中一种最优方案为：将  除以 ，得到序列 。
对于第二次询问，其中一种最优方案为：将  除以 ，得到序列 。
对于第三次询问，其中一种最优方案为：将  除以 ，再将  除以 ，得到序列 。