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;
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,tune=native")
template <typename T>
void print(T&& x) {
  cout << x << "\n";
}
template <typename T, typename... S>
void print(T&& x, S&&... y) {
  cout << x << ' ';
  print(y...);
}
const int Mod = 1000000007, Mod2 = 998244353;
const int MOD = Mod;
const int maxn = 200005;
int n, q, a[maxn], lpd[5100000], ans[1100000], cur, y, maxpos[15];
vector<int> pr;
vector<pair<int, int> > vec[5100000];
struct Query {
  int l, r, id;
} qry[1100000];
void hhhhauraorz() {
  lpd[0] = lpd[1] = 0;
  for (int i = (2); i < ((int)(5100000)); i++) {
    if (!lpd[i]) {
      lpd[i] = i;
      pr.push_back(i);
    }
    for (auto p : pr) {
      if (p * i >= 5100000) break;
      lpd[p * i] = p;
      if (i % p == 0) break;
    }
  }
  cin >> n >> q;
  for (int i = (0); i < ((int)(n)); i++) cin >> a[i];
  for (int i = (0); i < ((int)(q)); i++) cin >> qry[i].l >> qry[i].r;
  for (int i = (0); i < ((int)(q)); i++) qry[i].l--, qry[i].r--, qry[i].id = i;
  sort(qry, qry + q, [](Query& i, Query& j) { return i.r < j.r; });
  vector<int> vec1;
  int x;
  for (int i = (0); i < ((int)(15)); i++) maxpos[i] = -1;
  for (int i = (0); i < ((int)(n)); i++) {
    vec1.clear();
    for (int j = a[i]; j > 1; j /= lpd[j]) {
      if (vec1.empty() || vec1.back() != lpd[j])
        vec1.push_back(lpd[j]);
      else
        vec1.pop_back();
    }
    for (auto j : vec1) 826;
    826;
    for (int mask = (0); mask < ((int)((1ll << (((int)vec1.size())))));
         mask++) {
      x = 1;
      for (int j = (0); j < ((int)(((int)vec1.size()))); j++)
        if (mask & (1ll << (j))) x *= vec1[j];
      y = __builtin_popcountll(mask);
      for (auto& [c, d] : vec[x])
        maxpos[c + ((int)vec1.size()) - 2 * y] =
            max(maxpos[c + ((int)vec1.size()) - 2 * y], d);
      while (((int)vec[x].size()) && vec[x].back().first >= ((int)vec1.size()))
        vec[x].pop_back();
      vec[x].push_back({((int)vec1.size()), i});
    }
    while (cur < q && qry[cur].r == i) {
      for (int j = (14); j >= ((int)(0)); j--)
        if (maxpos[j] >= qry[cur].l) ans[qry[cur].id] = j;
      826;
      cur++;
    }
  }
  for (int i = (0); i < ((int)(q)); i++) print(ans[i]);
}
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int t;
  t = 1;
  while (t--) hhhhauraorz();
  return 0;
}