We call an array $b_1, b_2, \ldots, b_m$ good, if there exist two indices $i \lt 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 \lt 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.

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