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 T>
inline void amin(T &x, const T &y) {
  if (y < x) x = y;
}
template <class T>
inline void amax(T &x, const T &y) {
  if (x < y) x = y;
}
template <class Iter>
void rprintf(const char *fmt, Iter begin, Iter end) {
  for (bool sp = 0; begin != end; ++begin) {
    if (sp)
      putchar(' ');
    else
      sp = true;
    printf(fmt, *begin);
  }
  putchar('\n');
}
const int MAX = 5100000;
int min_factor[MAX + 1];
int normal[MAX + 1];
int pc[MAX + 1];
void init() {
  for (int i = 2; i <= MAX; i += 2) min_factor[i] = 2;
  for (int i = 3; i <= MAX; i += 3)
    if (!min_factor[i]) min_factor[i] = 3;
  for (int i = 5, d = 2; i * i <= MAX;) {
    if (!min_factor[i]) {
      min_factor[i] = i;
      for (int j = i * i; j <= MAX; j += i)
        if (!min_factor[j]) min_factor[j] = i;
    }
    i += d;
    d = 6 - d;
  }
  for (int i = 2; i <= MAX; i++) {
    if (min_factor[i] == 0) min_factor[i] = i;
  }
  for (int i = 0, i_len = (MAX + 1); i < i_len; ++i) normal[i] = i;
  for (int i = 2; i <= MAX; i++)
    if (min_factor[i] == i) {
      for (int k = i; k <= MAX; k += i) {
        int cnt = 0;
        while (normal[k] % i == 0) {
          normal[k] /= i;
          cnt++;
        }
        if (cnt & 1) {
          normal[k] *= i;
          pc[k]++;
        }
      }
    }
}
void rec(int x, int acc, vector<int> &ret) {
  if (x == 1) {
    ret.push_back(acc);
  } else {
    int p = min_factor[x];
    rec(x / p, acc, ret);
    rec(x / p, acc * p, ret);
  }
}
vector<int> divisors(int x) {
  vector<int> ret;
  rec(x, 1, ret);
  return ret;
}
int N, Q;
int A[200111];
int ans[1050111];
int dp[MAX + 1][8];
int right_most[20];
struct Query {
  int l, r, i;
  bool operator<(const Query &y) const { return r < y.r; }
};
vector<Query> VQ;
void MAIN() {
  init();
  scanf("%d%d", &N, &Q);
  VQ.reserve(Q);
  for (int i = 0, i_len = (N); i < i_len; ++i) {
    scanf("%d", A + i);
  }
  for (int i = 0, i_len = (Q); i < i_len; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    l--;
    Query q;
    q.l = l;
    q.r = r;
    q.i = i;
    VQ.push_back(q);
  }
  sort(VQ.begin(), VQ.end());
  int cur = 0;
  memset(dp, -1, sizeof dp);
  memset(right_most, -1, sizeof right_most);
  for (__typeof((VQ).begin()) e = (VQ).begin(), e_end = (VQ).end(); e != e_end;
       ++e) {
    int l = e->l;
    int r = e->r;
    while (cur < r) {
      int x = normal[A[cur]];
      vector<int> D = divisors(x);
      for (__typeof((D).begin()) f = (D).begin(), f_end = (D).end(); f != f_end;
           ++f) {
        int c = pc[x / *f];
        for (int t = 0, t_len = (8); t < t_len; ++t) {
          amax(right_most[c + t], dp[*f][t]);
        }
        dp[*f][c] = cur;
      }
      cur++;
    }
    ans[e->i] = 1000;
    for (int t = 0, t_len = (20); t < t_len; ++t)
      if (right_most[t] >= e->l) {
        ans[e->i] = t;
        break;
      }
  }
  for (int i = 0, i_len = (Q); i < i_len; ++i) printf("%d\n", ans[i]);
}
int main() {
  int TC = 1;
  for (int tc = 0, tc_len = (TC); tc < tc_len; ++tc) MAIN();
  return 0;
}