题目描述

给你一个 $n$ 个数的序列 $a_i$，和 $q$ 次询问，每次询问一段区间 $[l,r]$，问 至少 要把这个区间分为几个子区间，才能使得每个子区间内的数的乘积等于这个子区间内所有数的 LCM 。

其中 LCM 为最小公倍数的含义。

输入格式

第一行包含 $2$ 个整数 $n$ 和 $q$ ( $1 \le n,q \le 10^5$ ) - 数组长度 $a$ 和查询次数。

下一行包含 $n$ 个整数 $a_1$ 、 $a_2$ 、 $\ldots$ 、 $a_n$ ( $1 \le a_i \le 10^5$ )--数组 $a$ 的元素。

接下来的每行 $q$ 都包含 $2$ 个整数 $l$ 和 $r$ ( $1 \le l \le r \le n$ )--即该查询区间的端点。

输出格式

对于每个查询，打印其答案。

6 3
2 3 10 7 5 14
1 6
2 4
3 5

3
1
2

样例解释

第一个查询询问的是整个数组。您可以将其划分为 $[2]$ 、 $[3,10,7]$ 和 $[5,14]$ 。第一个子范围的乘积和 LCM 等于 $2$ 。第二个子范围的乘积和 LCM 等于 $210$ 。第三个子区间的乘积和 LCM 等于 $70$ 。另一种可能的分割是 $[2,3]$ 、 $[10,7]$ 和 $[5,14]$ 。

第二个查询涉及范围 $(2,4)$ 。它的乘积等于它的 LCM，因此不需要进一步分割。

最后一个查询涉及范围 $(3,5)$ 。可以将其划分为 $[10,7]$ 和 $[5]$ 。