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 = 200005, maxm = 5100005, N = 5100000;
int prime[maxm / 10], mn[maxn * 3], dv[maxm];
int lst[maxm][8], res[maxn * 5], n, Q, cnt, tn;
bool vis[maxm];
vector<pair<int, int> > vec[maxn], qr[maxn];
void update(int x, int w) {
  x += tn - 1;
  mn[x] = min(mn[x], w);
  while (x > 0) {
    x = (x - 1) >> 1;
    mn[x] = min(mn[x], w);
  }
}
int query(int a, int b, int l = 0, int r = tn, int k = 0) {
  if (a <= l && b >= r) return mn[k];
  if (a >= r || b <= l) return INT_MAX;
  int mid = (l + r) >> 1;
  return min(query(a, b, l, mid, k * 2 + 1), query(a, b, mid, r, k * 2 + 2));
}
int main() {
  scanf("%d%d", &n, &Q);
  for (int i = 2; i <= N; i++) {
    if (!vis[i]) {
      prime[++cnt] = i;
      dv[i] = i;
    }
    for (int j = 1; j <= cnt; j++) {
      int p = prime[j], q = i * p;
      if (q > N) break;
      vis[q] = true;
      dv[q] = p;
      if (i % p == 0) break;
    }
  }
  for (int i = 1; i <= n; i++) {
    int t, temp[20];
    memset(temp, 0, sizeof(temp));
    scanf("%d", &t);
    vector<int> d;
    while (t > 1) {
      int p = dv[t], c = 0;
      while (t % p == 0) t /= p, ++c;
      if (c & 1) d.push_back(p);
    }
    t = d.size();
    for (int j = 0; j < 1 << t; j++) {
      int mul = 1, c = 0;
      for (int k = 0; k < t; k++)
        if (j >> k & 1) mul *= d[k], ++c;
      for (int k = 0; k < 8; k++)
        if (lst[mul][k]) temp[t - c + k] = max(temp[t - c + k], lst[mul][k]);
      lst[mul][t - c] = i;
    }
    for (int j = 0; j < 20; j++)
      if (temp[j]) vec[i].push_back(pair<int, int>(j, temp[j]));
  }
  for (tn = 1; tn < n; tn <<= 1)
    ;
  memset(mn, 0x3f, sizeof(mn));
  for (int i = 1; i <= Q; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    qr[b].push_back(pair<int, int>(a, i));
  }
  for (int i = 1; i <= n; i++) {
    for (pair<int, int> p : vec[i]) update(p.second - 1, p.first);
    for (pair<int, int> p : qr[i]) res[p.second] = query(p.first - 1, i);
  }
  for (int i = 1; i <= Q; i++) printf("%d\n", res[i]);
  return 0;
}