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;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 194598;
const int MAXQ = 1049658;
const int MAXA = 5032107;
const int MAXP = 8;
const int MAXCOST = 12;
const int MAXS = 4 * MAXN;
int n, nq;
int a[MAXN];
int ql[MAXQ], qr[MAXQ];
int pmn[MAXA + 1];
int b[MAXN];
vector<int> bp[MAXN];
int nxtocc[MAXA + 1][MAXP + 1];
int nxtcost[MAXN][MAXCOST + 1];
void updnxt(int idx, int at, int val, int cost) {
  if (at >= ((int)(bp[idx]).size())) {
    int lim = min(MAXP, MAXCOST - cost);
    for (int othcost = (0); othcost <= (lim); ++othcost)
      if (nxtocc[val][othcost] != -1 &&
          (nxtcost[idx][cost + othcost] == -1 ||
           nxtocc[val][othcost] < nxtcost[idx][cost + othcost]))
        nxtcost[idx][cost + othcost] = nxtocc[val][othcost];
    nxtocc[val][cost] = idx;
  } else {
    updnxt(idx, at + 1, val, cost);
    updnxt(idx, at + 1, val * bp[idx][at], cost - 1);
  }
}
struct Seg {
  int cost;
  int sval[MAXS];
  void sinit(int x, int l, int r) {
    if (l == r) {
      sval[x] = nxtcost[l][cost] == -1 ? INT_MAX : nxtcost[l][cost];
    } else {
      int m = l + (r - l) / 2;
      sinit(2 * x + 1, l, m);
      sinit(2 * x + 2, m + 1, r);
      sval[x] = min(sval[2 * x + 1], sval[2 * x + 2]);
    }
  }
  int sget(int x, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
      return sval[x];
    } else {
      int m = l + (r - l) / 2, ret = INT_MAX;
      if (L <= m) ret = min(ret, sget(2 * x + 1, l, m, L, R));
      if (m + 1 <= R) ret = min(ret, sget(2 * x + 2, m + 1, r, L, R));
      return ret;
    }
  }
};
Seg seg[MAXCOST + 1];
void run() {
  scanf("%d%d", &n, &nq);
  for (int i = (0); i < (n); ++i) scanf("%d", &a[i]);
  for (int i = (0); i < (nq); ++i)
    scanf("%d%d", &ql[i], &qr[i]), --ql[i], --qr[i];
  memset(pmn, -1, sizeof(pmn));
  for (int i = (2); i <= (MAXA); ++i)
    if (pmn[i] == -1)
      for (int j = i; j <= MAXA; j += i)
        if (pmn[j] == -1) pmn[j] = i;
  for (int i = (0); i < (n); ++i) {
    int x = a[i];
    b[i] = 1;
    bp[i].clear();
    while (x != 1) {
      int p = pmn[x];
      assert(x % p == 0);
      x /= p;
      if (((int)(bp[i]).size()) != 0 && bp[i].back() == p)
        b[i] /= p, bp[i].pop_back();
      else
        b[i] *= p, bp[i].push_back(p);
    }
  }
  memset(nxtocc, -1, sizeof(nxtocc));
  memset(nxtcost, -1, sizeof(nxtcost));
  for (int i = n - 1; i >= 0; --i) updnxt(i, 0, 1, ((int)(bp[i]).size()));
  for (int i = (0); i < (n); ++i)
    for (int j = (1); j <= (MAXCOST); ++j)
      if (nxtcost[i][j - 1] != -1 &&
          (nxtcost[i][j] == -1 || nxtcost[i][j - 1] < nxtcost[i][j]))
        nxtcost[i][j] = nxtcost[i][j - 1];
  for (int j = (0); j <= (MAXCOST); ++j) {
    seg[j].cost = j;
    seg[j].sinit(0, 0, n - 1);
  }
  for (int i = (0); i < (nq); ++i) {
    int l = -1, h = MAXCOST;
    while (l + 1 < h) {
      int m = l + (h - l) / 2;
      int cur = seg[m].sget(0, 0, n - 1, ql[i], qr[i]);
      if (cur <= qr[i])
        h = m;
      else
        l = m;
    }
    printf("%d\n", h);
  }
}
int main() {
  run();
  return 0;
}