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 long long mod = 1000000007;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
namespace Factor {
const int N = 1010000;
long long C, fac[10010], n, mut, a[1001000];
int T, cnt, i, l, prime[N], p[N], psize, _cnt;
long long _e[100], _pr[100];
vector<long long> d;
vector<pair<long long, long long> > dd;
inline long long mul(long long a, long long b, long long p) {
  if (p <= 1000000000)
    return a * b % p;
  else if (p <= 1000000000000ll)
    return (((a * (b >> 20) % p) << 20) + (a * (b & ((1 << 20) - 1)))) % p;
  else {
    long long d = (long long)floor(a * (long double)b / p + 0.5);
    long long ret = (a * b - d * p) % p;
    if (ret < 0) ret += p;
    return ret;
  }
}
void prime_table() {
  int i, j, tot, t1;
  for (i = 1; i <= psize; i++) p[i] = i;
  for (i = 2, tot = 0; i <= psize; i++) {
    if (p[i] == i) prime[++tot] = i;
    for (j = 1; j <= tot && (t1 = prime[j] * i) <= psize; j++) {
      p[t1] = prime[j];
      if (i % prime[j] == 0) break;
    }
  }
}
void init(int ps) {
  psize = ps;
  prime_table();
}
long long powl(long long a, long long n, long long p) {
  long long ans = 1;
  for (; n; n >>= 1) {
    if (n & 1) ans = mul(ans, a, p);
    a = mul(a, a, p);
  }
  return ans;
}
bool witness(long long a, long long n) {
  int t = 0;
  long long u = n - 1;
  for (; ~u & 1; u >>= 1) t++;
  long long x = powl(a, u, n), _x = 0;
  for (; t; t--) {
    _x = mul(x, x, n);
    if (_x == 1 && x != 1 && x != n - 1) return 1;
    x = _x;
  }
  return _x != 1;
}
bool miller(long long n) {
  if (n < 2) return 0;
  if (n <= psize) return p[n] == n;
  if (~n & 1) return 0;
  for (int j = 0; j <= 7; j++)
    if (witness(rand() % (n - 1) + 1, n)) return 0;
  return 1;
}
long long gcd(long long a, long long b) {
  long long ret = 1;
  while (a != 0) {
    if ((~a & 1) && (~b & 1))
      ret <<= 1, a >>= 1, b >>= 1;
    else if (~a & 1)
      a >>= 1;
    else if (~b & 1)
      b >>= 1;
    else {
      if (a < b) swap(a, b);
      a -= b;
    }
  }
  return ret * b;
}
long long rho(long long n) {
  for (;;) {
    long long X = rand() % n, Y, Z, T = 1, *lY = a, *lX = lY;
    int tmp = 20;
    C = rand() % 10 + 3;
    X = mul(X, X, n) + C;
    *(lY++) = X;
    lX++;
    Y = mul(X, X, n) + C;
    *(lY++) = Y;
    for (; X != Y;) {
      long long t = X - Y + n;
      Z = mul(T, t, n);
      if (Z == 0) return gcd(T, n);
      tmp--;
      if (tmp == 0) {
        tmp = 20;
        Z = gcd(Z, n);
        if (Z != 1 && Z != n) return Z;
      }
      T = Z;
      Y = *(lY++) = mul(Y, Y, n) + C;
      Y = *(lY++) = mul(Y, Y, n) + C;
      X = *(lX++);
    }
  }
}
void _factor(long long n) {
  for (int i = 0; i < cnt; i++) {
    if (n % fac[i] == 0) n /= fac[i], fac[cnt++] = fac[i];
  }
  if (n <= psize) {
    for (; n != 1; n /= p[n]) fac[cnt++] = p[n];
    return;
  }
  if (miller(n))
    fac[cnt++] = n;
  else {
    long long x = rho(n);
    _factor(x);
    _factor(n / x);
  }
}
void dfs(long long x, int dep) {
  if (dep == _cnt)
    d.push_back(x);
  else {
    dfs(x, dep + 1);
    for (int i = 1; i <= _e[dep]; i++) dfs(x *= _pr[dep], dep + 1);
  }
}
void dfs(long long x, int dep, int diff) {
  if (dep == _cnt)
    dd.push_back(make_pair(x, diff));
  else {
    dfs(x, dep + 1, diff + 1);
    dfs(x * _pr[dep], dep + 1, diff);
  }
}
void norm() {
  sort(fac, fac + cnt);
  _cnt = 0;
  for (int i = 0; i < cnt; i++)
    if (i == 0 || fac[i] != fac[i - 1])
      _pr[_cnt] = fac[i], _e[_cnt++] = 1;
    else
      _e[_cnt - 1]++;
  for (int i = 0; i < _cnt; i++) _e[i] %= 2;
  int cc = 0;
  for (int i = 0; i < _cnt; i++) {
    if (_e[i] != 0) _pr[cc++] = _pr[i];
  }
  _cnt = cc;
}
vector<long long> getd() {
  d.clear();
  dfs(1, 0);
  return d;
}
vector<pair<long long, long long> > getdd() {
  dd.clear();
  dfs(1, 0, 0);
  return dd;
}
vector<long long> factor(long long n) {
  cnt = 0;
  _factor(n);
  norm();
  return getd();
}
vector<pair<long long, long long> > reduce(long long n) {
  cnt = 0;
  _factor(n);
  norm();
  return getdd();
}
vector<pair<long long, long long> > factorG(long long n) {
  cnt = 0;
  _factor(n);
  norm();
  vector<pair<long long, long long> > d;
  for (int i = 0; i < _cnt; i++) d.push_back(make_pair(_pr[i], _e[i]));
  return d;
}
bool is_primitive(long long a, long long p) {
  assert(miller(p));
  vector<pair<long long, long long> > D = factorG(p - 1);
  for (int i = 0; i < ((int)(D).size()); i++)
    if (powl(a, (p - 1) / D[i].first, p) == 1) return 0;
  return 1;
}
}  // namespace Factor
const int N = 201000, M = 1100000;
int dis[5032110][8];
int a[N], n, q, minr[N][20];
int hv[N], ret[M], l[M], r[M];
int main() {
  Factor::init(1000000);
  scanf("%d%d", &n, &q);
  for (int i = 1; i < n + 1; i++) scanf("%d", a + i);
  memset(dis, 0x20, sizeof(dis));
  for (int i = n + 1 - 1; i >= 1; i--) {
    vector<pair<long long, long long> > d = Factor::reduce(a[i]);
    for (int j = 0; j < 15; j++) {
      minr[i][j] = n + 1;
    }
    for (auto p : d) {
      for (int d2 = 0; d2 <= 7; d2++) {
        minr[i][p.second + d2] = min(minr[i][p.second + d2], dis[p.first][d2]);
      }
    }
    for (auto p : d) dis[p.first][p.second] = i;
    for (int j = 1; j < 15; j++) minr[i][j] = min(minr[i][j], minr[i][j - 1]);
  }
  for (int i = 0; i < q; i++) scanf("%d%d", l + i, r + i), ret[i] = -1;
  for (int ans = 0; ans <= 14; ans++) {
    for (int i = 1; i < n + 1; i++) {
      hv[i] = minr[i][ans];
    }
    for (int i = n - 1; i >= 1; i--) hv[i] = min(hv[i], hv[i + 1]);
    for (int i = 0; i < q; i++)
      if (ret[i] == -1) {
        if (hv[l[i]] <= r[i]) ret[i] = ans;
      }
  }
  for (int i = 0; i < q; i++) printf("%d\n", ret[i]);
}