A14193 | 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)](https://en.wikipedia.org/wiki/Least_common_multiple).

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.

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.

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