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;
template <class TH>
void _dbg(const char *sdbg, TH h) {
  cerr << sdbg << "=" << h << "\n";
}
template <class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
  while (*sdbg != ',') cerr << *sdbg++;
  cerr << "=" << h << ",";
  _dbg(sdbg + 1, a...);
}
const int N = (1 << 18);
int test;
int n, q;
int t[N];
int res[N * 5];
vector<pair<int, int> > g[N];
vector<int> dz;
vector<pair<int, int> > kek;
int dp[5 * 5 * N + 100000][8];
int load[4 * N + 7];
int odp[N][15];
void zrob(int x) {
  dz.clear();
  kek.clear();
  int y = x;
  for (int i = 2; i * i <= x; i++) {
    int cou = 0;
    while (x % i == 0) {
      cou++;
      x /= i;
    }
    if (cou % 2) {
      dz.push_back(i);
    }
  }
  if (x > 1) {
    dz.push_back(x);
  }
  int h = dz.size();
  for (int mask = 0; mask < (1 << h); mask++) {
    int pom = 1;
    int pom1 = 0;
    for (int i = 0; i < h; i++) {
      if (mask & (1 << i)) {
        pom *= dz[i];
        pom1++;
      }
    }
    kek.emplace_back(pom, h - pom1);
  }
}
void ins(int v, int x) {
  v += N - 1;
  load[v] = min(load[v], x);
  while (v >= 1) {
    v /= 2;
    load[v] = min(load[v * 2], load[v * 2 + 1]);
  }
  return;
}
void query(int x, int l, int y) {
  for (int i = 0; i <= (7); ++i) {
    if (dp[x][i] > 0) {
      odp[y][l + i] = max(odp[y][l + i], dp[x][i]);
    }
  }
}
void dodaj(int x, int poz, int cost) {
  dp[x][cost] = max(dp[x][cost], poz);
  return;
}
int que(int l, int r, int v = 1, int L = 1, int R = N) {
  if (L > r || R < l) return 1000000007;
  if (L >= l && R <= r) {
    return load[v];
  }
  return min(que(l, r, v * 2, L, (L + R) / 2),
             que(l, r, v * 2 + 1, (L + R) / 2 + 1, R));
}
void solve() {
  cin >> n >> q;
  for (int i = 1; i <= (n); ++i) {
    cin >> t[i];
  }
  for (int i = 1; i <= (q); ++i) {
    int l, r;
    cin >> l >> r;
    g[r].emplace_back(l, i);
  }
  for (int i = 1; i <= (4 * N); ++i) load[i] = 1000000007;
  for (int i = 1; i <= (n); ++i) {
    zrob(t[i]);
    for (auto it : kek) {
      query(it.first, it.second, i);
      dodaj(it.first, i, it.second);
    }
    for (int j = 0; j <= (15); ++j) {
      ins(odp[i][j], j);
    }
    for (auto it : g[i]) {
      res[it.second] = que(it.first, i);
    }
  }
  for (int i = 1; i <= (q); ++i) {
    cout << res[i] << '\n';
  }
  return;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout.precision(10);
  cout << fixed;
  test = 1;
  for (int i = 1; i <= test; i++) {
    solve();
  }
  return 0;
}