这次婴儿 Ehab 只会切割,不会粘住。他从一张纸开始,上面写着一个长度为 $$$n$$$ 的数组 $$$a$$$,然后他执行以下操作:
- 他选择一个范围 $$$(l, r)$$$ 并剪切子段 $$$a_l, a_{l + 1}, \ldots, a_r$$$ ,删除数组的其余部分。
- 然后他将此范围切割成多个子范围。
- 为了添加数论趣味,他要求每个子范围的元素的乘积必须等于其最小公倍数 (LCM)。
正式地,他将 $$$a_l, a_{l + 1}, \ldots, a_r$$$ 的元素划分为连续的子数组,使得每个子数组的乘积等于其 LCM。现在,对于 $$$q$$$ 独立范围 $$$(l, r)$$$,告诉 Baby Ehab 他需要的最小子数组数。
输入
第一行包含 $$$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$$$) - 此查询间隔的端点。
输出
对于每个查询,将其答案打印在新行上。
示例
输入 #1
6 3 2 3 10 7 5 14 1 6 2 4 3 5
输出 #1
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]$$$。