CF1516D.Cut

This time Baby Ehab will only cut and not stick. He starts with a piece of paper with an array $a$ of length $n$ written on it, and then he does the following:

• he picks a range $(l, r)$ and cuts the subsegment $a_l, a_{l + 1}, \ldots, a_r$ out, removing the rest of the array.
• he then cuts this range into multiple subranges.
• to add a number theory spice to it, he requires that the elements of every subrange must have their product equal to their least common multiple (LCM).

Formally, he partitions the elements of $a_l, a_{l + 1}, \ldots, a_r$ into contiguous subarrays such that the product of every subarray is equal to its LCM. Now, for $q$ independent ranges $(l, r)$, tell Baby Ehab the minimum number of subarrays he needs.

这一次，Baby 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 所需子数组的最小数量。

The first line contains $2$ integers $n$ and $q$ ($1 \le n,q \le 10^5$) — the length of the array $a$ and the number of queries.

The next line contains $n$ integers $a_1$, $a_2$, $\ldots$, $a_n$ ($1 \le a_i \le 10^5$) — the elements of the array $a$.

Each of the next $q$ lines contains $2$ integers $l$ and $r$ ($1 \le l \le r \le n$) — the endpoints of this query's interval.

第一行包含两个整数 $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$ 行，每行包含两个整数 $l$ 和 $r$（$1 \le l \le r \le n$）—— 表示该次查询所对应的区间端点。

For each query, print its answer on a new line.

对于每个查询，在新行中输出其答案。

The first query asks about the whole array. You can partition it into $[2]$, $[3,10,7]$, and $[5,14]$. The first subrange has product and LCM equal to $2$. The second has product and LCM equal to $210$. And the third has product and LCM equal to $70$. Another possible partitioning is $[2,3]$, $[10,7]$, and $[5,14]$.

The second query asks about the range $(2,4)$. Its product is equal to its LCM, so you don't need to partition it further.

The last query asks about the range $(3,5)$. You can partition it into $[10,7]$ and $[5]$.

第一个查询针对整个数组。你可以将其划分为 $[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]$ 两个子区间。