如果存在两个索引 $$$i < j$$$ 使得 $$$b_i \cdot b_j$$$ 是一个完全平方数,我们称数组 $$$b_1, b_2, \ldots, b_m$$$ 为好。
给定一个数组 $$$b_1, b_2, \ldots, b_m$$$,在一个操作中您可以执行以下操作之一:
- 任意元素 $$$b_i$$$ 乘以任意素数 $$$p$$$;
- 如果 $$$b_i$$$ 可被 $$$p$$$ 整除,则任何元素 $$$b_i$$$ 除以质数 $$$p$$$。
令 $$$f(b_1, b_2, \ldots, b_m)$$$ 为使数组 $$$b$$$ 良好所需的最小操作数。
给你一个 $$$n$$$ 整数数组 $$$a_1, a_2, \ldots, a_n$$$ 和 $$$q$$$ 形式的查询 $$$l_i, r_i$$$。对于每个查询输出 $$$f(a_{l_i}, a_{l_i + 1}, \ldots, a_{r_i})$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 194\,598$$$, $$$1 \le q \le 1\,049\,658$$$) — 数组的长度和查询的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 5\,032\,107$$$) — 数组的元素。
接下来的 $$$q$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i < r_i \le n$$$) — 查询的参数。
输出
输出 $$$q$$$ 行 — 每个查询的答案按照输入中给出的顺序排列。
示例
输入 #1
10 10 34 37 28 16 44 36 43 50 22 13 1 3 4 8 6 10 9 10 3 10 8 9 5 6 1 4 1 7 2 6
输出 #1
2 0 1 3 0 1 1 1 0 0
注意
在第一个样本的第一个查询中,您可以将第二个数字乘以 7 得到 259,将第三个数字乘以 37 得到 1036。然后 $$$a_2 \cdot a_3 = 268\,324 = 518^2$$$。
在第二个查询子数组中已经很好了,因为 $$$a_4 \cdot a_6 = 24^2$$$。
在第三个查询中,您可以将 50 除以 2 得到 25。然后 $$$a_6 \cdot a_8 = 30^2$$$。