A12042 | Make Square

We call an array $b_1, b_2, \ldots, b_m$ good, if there exist two indices $i < j$ such that $b_i \cdot b_j$ is a [perfect square](https://en.wikipedia.org/wiki/Square_number).

Given an array $b_1, b_2, \ldots, b_m$ , in one action you can perform one of the following:

- multiply any element $b_i$ by any prime $p$ ;
- divide any element $b_i$ by prime $p$ , if $b_i$ is divisible by $p$ .

Let $f(b_1, b_2, \ldots, b_m)$ be the minimum number of actions needed to make the array $b$ good.

You are given an array of $n$ integers $a_1, a_2, \ldots, a_n$ and $q$ queries of the form $l_i, r_i$ . For each query output $f(a_{l_i}, a_{l_i + 1}, \ldots, a_{r_i})$ .

The first line contains two integers $n$ and $q$ ( $2 \le n \le 194\,598$ , $1 \le q \le 1\,049\,658$ ) — the length of the array and the number of queries.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 5\,032\,107$ ) — the elements of the array.

Each of the next $q$ lines contains two integers $l_i$ and $r_i$ ( $1 \le l_i < r_i \le n$ ) — the parameters of a query.

Output $q$ lines — the answers for each query in the order they are given in the input.