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 x, primes[350588], p = 0;
vector<vector<int> > pfs(194598);
bool isprime[5032107 + 1];
unordered_map<int, int> rankd;
int dp[8][5032107], ans[15][194598], a[194598];
void getprimes() {
  for (int i = 2; i <= 5032107; i++) isprime[i] = true;
  for (int i = 2; i * i <= 5032107; i++) {
    if (isprime[i])
      for (int j = i + i; j <= 5032107; j += i) isprime[j] = false;
  }
  for (int i = 2; i <= 5032107; i++)
    if (isprime[i]) primes[p++] = i;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  getprimes();
  int n, x, i, j, cnt = 0, q;
  scanf("%d %d", &n, &q);
  for (i = 0; i < 8; i++)
    for (j = 0; j < 5032107; j++) dp[i][j] = -1;
  for (i = 0; i < 15; i++)
    for (j = 0; j < n; j++) ans[i][j] = -1;
  for (i = 0; i < n; i++) {
    scanf("%d", &x);
    for (j = 0; primes[j] * primes[j] <= x; j++) {
      if (x % primes[j] != 0) continue;
      while (x % (primes[j] * primes[j]) == 0) x /= (primes[j] * primes[j]);
      if (x % primes[j] == 0) {
        pfs[i].push_back(primes[j]);
        x /= primes[j];
      }
    }
    if (x > 1) pfs[i].push_back(x);
    a[i] = 1;
    for (auto it : pfs[i]) a[i] *= it;
    int jp = pfs[i].size();
    for (j = 0; j < (1 << jp); j++) {
      int curr = 1;
      for (int m = 0; m < jp; m++)
        if ((1 << m) & j) {
          curr *= pfs[i][m];
        }
      if (rankd.find(curr) != rankd.end()) {
        int sol = jp - __builtin_popcount(j), jj;
        for (jj = 0; jj < 8; jj++) {
          if (jj + sol > 14) break;
          ans[jj + sol][i] = max(ans[jj + sol][i], dp[jj][rankd[curr]]);
        }
      }
    }
    for (j = 0; j < (1 << jp); j++) {
      int curr = 1;
      for (int m = 0; m < jp; m++)
        if ((1 << m) & j) {
          curr *= pfs[i][m];
        }
      if (rankd.find(curr) == rankd.end()) {
        rankd.insert(make_pair(curr, cnt++));
      }
      int req = jp - __builtin_popcount(j);
      dp[req][rankd[curr]] = i;
    }
  }
  for (i = 1; i < n; i++) {
    for (j = 0; j < 15; j++) ans[j][i] = max(ans[j][i], ans[j][i - 1]);
  }
  while (q--) {
    int l, r, sol;
    scanf("%d %d", &l, &r);
    for (sol = 0; sol < 15; sol++)
      if (ans[sol][r - 1] >= l - 1) break;
    printf("%d\n", sol);
  }
  return 0;
}