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 MAXN = 2e5, MAXQ = 1 << 21, MAXM = 5100000;
int sito[MAXM];
void eratosten() {
  for (int i = (2); i < (MAXM); i++)
    if (!sito[i])
      for (int j = i; j < MAXM; j += i) sito[j] = i;
}
vector<int> Prosti(int x) {
  vector<int> R;
  for (; x > 1;) {
    int pr = sito[x], pot = 0;
    for (; sito[x] == pr; x /= sito[x], pot++)
      ;
    if (pot % 2) R.push_back(pr);
  }
  return R;
}
struct event {
  int r, val;
};
vector<event> Ev[MAXN];
int gdje[MAXM][8];
int p[MAXN];
void add_num(int pos) {
  vector<int> R = Prosti(p[pos]);
  int sz = (int)R.size();
  for (int msk = (0); msk < (1 << sz); msk++) {
    int umn = 1;
    for (int j = (0); j < (sz); j++)
      if (msk >> j & 1) umn *= R[j];
    gdje[umn][sz - __builtin_popcount(msk)] = pos;
  }
}
int n, brq;
void gen_events() {
  for (int i = (0); i < (MAXM); i++)
    for (int j = (0); j < (8); j++) gdje[i][j] = MAXN - 1;
  int mn[20];
  for (int i = n - 1; i >= 0; i--) {
    for (int j = (0); j < (20); j++) mn[j] = MAXN - 1;
    vector<int> R = Prosti(p[i]);
    int sz = (int)R.size();
    for (int msk = (0); msk < (1 << sz); msk++) {
      int umn = 1;
      for (int j = (0); j < (sz); j++)
        if (msk >> j & 1) umn *= R[j];
      for (int ost = (0); ost < (8); ost++) {
        int pos = gdje[umn][ost];
        int val = ost + sz - __builtin_popcount(msk);
        mn[val] = min(mn[val], pos);
      }
    }
    for (int j = (0); j < (20); j++) Ev[i].push_back({mn[j], j});
    add_num(i);
  }
}
int fen[MAXN];
vector<pair<int, int> > Q[MAXN];
int sol[MAXQ];
void upd(int pos, int val) {
  pos++;
  for (; pos < MAXN; pos += pos & -pos) fen[pos] = min(fen[pos], val);
}
int get(int pos) {
  pos++;
  int ret = MAXN;
  for (; pos; pos -= pos & -pos) ret = min(ret, fen[pos]);
  return ret;
}
void solve() {
  for (int i = (0); i < (MAXN); i++) fen[i] = MAXN;
  for (int i = n - 1; i >= 0; i--) {
    for (auto it : Ev[i]) upd(it.r, it.val);
    for (auto q : Q[i]) sol[q.second] = get(q.first);
  }
}
int main() {
  eratosten();
  scanf("%d%d", &n, &brq);
  for (int i = (0); i < (n); i++) scanf("%d", &p[i]);
  for (int i = (0); i < (brq); i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    l--;
    r--;
    Q[l].push_back(pair<int, int>(r, i));
  }
  gen_events();
  solve();
  for (int i = (0); i < (brq); i++) printf("%d\n", sol[i]);
  return 0;
}