H. Make Square
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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})$.

Input

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

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

Example
Input
10 1034 37 28 16 44 36 43 50 22 131 34 86 109 103 108 95 61 41 72 6
Output
2013011100
Note

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