CF1028H.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.

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.

In the first query of the first sample you can multiply second number by 7 to get 259 and multiply the third one by 37 to get 1036. Then $a_2 \cdot a_3 = 268\,324 = 518^2$ .

In the second query subarray is already good because $a_4 \cdot a_6 = 24^2$ .

In the third query you can divide 50 by 2 to get 25. Then $a_6 \cdot a_8 = 30^2$ .