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

Given an array b_1, b_2, …, 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, …, 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, …, a_n and q queries of the form l_i, r_i. For each query output f(a_{l_i}, a_{l_i + 1}, …, a_{r_i}).

Input

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

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 5 032 107) — the elements of the array.

Each of the next q lines contains two integers l_i and r_i (1 ≤ l_i < r_i ≤ 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 10
34 37 28 16 44 36 43 50 22 13
1 3
4 8
6 10
9 10
3 10
8 9
5 6
1 4
1 7
2 6


Output

2
0
1
3
0
1
1
1
0
0

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 ⋅ a_3 = 268 324 = 518^2.

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

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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int M = 5.1e6, N = 2e5, Q = 1.1e6, P = 8;
int n, q, a[N], mdiv[M], ans[Q];
vector<pair<int, int>> qs[N];
int last[M][P], best[2 * P];
void relax(int gcd, int add, int ind) {
  for (int p = 0; p < P; p++)
    if (last[gcd][p]) {
      best[p + add] = max(best[p + add], last[gcd][p]);
    }
  for (int p = 1; p < 2 * P; p++) best[p] = max(best[p], best[p - 1]);
  last[gcd][add] = ind;
}
int main() {
  iota(mdiv, mdiv + M, 0);
  for (int d = 2; d * d <= M; d++)
    if (mdiv[d] == d) {
      for (int x = d + d; x < M; x += d)
        if (mdiv[x] == x) mdiv[x] = d;
    }
  cin >> n >> q;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    qs[r].emplace_back(l, i);
  }
  for (int i = 1; i <= n; i++) {
    int sz = 0;
    static int fact[10];
    while (a[i] > 1) {
      int d = mdiv[a[i]], flag = 0;
      while (mdiv[a[i]] == d) {
        flag = 1 - flag;
        a[i] /= d;
      }
      if (flag) fact[sz++] = d;
    }
    static int mul[1 << P], pop[1 << P];
    for (int mask = 0; mask < (1 << sz); mask++) {
      if (mask == 0) {
        mul[mask] = 1;
        pop[mask] = 0;
      } else {
        int bit = __builtin_ctz(mask);
        mul[mask] = mul[mask - (1 << bit)] * fact[bit];
        pop[mask] = pop[mask - (1 << bit)] + 1;
      }
      relax(mul[mask], sz - pop[mask], i);
      for (auto li : qs[i]) {
        int l, ind;
        tie(l, ind) = li;
        int &res = ans[ind];
        res = 2 * P;
        for (int p = 0; p < 2 * P; p++)
          if (best[p] >= l) {
            res = p;
            break;
          }
        assert(res < 2 * P);
      }
    }
  }
  for (int i = 0; i < q; i++) cout << ans[i] << '\n';
  return 0;
}