cut

Problem Source

CF 1516D

Problem Description

You are given a sequence $a_1, a_2, \dots, a_n$ of length $n$, and $q$ queries.

Each query gives an interval $[l, r]$. We want to partition $a_l, a_{l+1}, \dots, a_r$ into several segments such that the LCM (least common multiple) of the numbers in each segment equals the product of the numbers in that segment.

For each query, find the minimum number of segments the interval can be partitioned into.

Input Format

The first line contains two integers $n, q$, the sequence length and the number of queries.

The second line contains $n$ integers: $a_1, a_2, \dots, a_n$.

The following $q$ lines each contain two integers $l, r$, representing one query.

Output Format

For each query, output one line containing an integer: the answer.

Sample Input

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

Sample Output

3
1
2

Constraints

For $100\%$ of the data, $1 \leq n, q \leq 10^5, 1 \leq a_i \leq 10^5, 1 \leq l \leq r \leq n$.