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 n, q, l, r, cur = 1;
int a[194698], ans[5032117 / 4];
int ne_ans[18], ne_pos[10][5032117], sm[5032117];
bool p[5032117];
vector<pair<int, int> > v[194698];
void backt_track(int now, int tot, vector<int>& prs, int ps) {
  if (now == ((int)prs.size())) {
    for (int i = 0; i <= 8; i++)
      ne_ans[i + tot] = max(ne_ans[i + tot], ne_pos[i][cur]);
    ne_pos[tot][cur] = ps;
    return;
  }
  cur *= prs[now];
  backt_track(now + 1, tot, prs, ps);
  cur /= prs[now];
  backt_track(now + 1, tot + 1, prs, ps);
}
vector<int> process(int x) {
  vector<int> res;
  while (x > 1) {
    int tut = sm[x];
    int tot = 0;
    while (sm[x] == tut) x /= tut, tot++;
    if (tot & 1) res.push_back(tut);
  }
  return res;
}
void sieve() {
  for (int i = 2; i < 5032117; i++) {
    if (!p[i]) {
      for (int j = i; j < 5032117; j += i) {
        if (!sm[j]) sm[j] = i;
        p[j] = 1;
      }
    }
  }
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i <= q; i++) {
    scanf("%d %d", &l, &r);
    v[r].push_back({l, i});
  }
  sieve();
  for (int i = 1; i <= n; i++) {
    vector<int> prs = process(a[i]);
    backt_track(0, 0, prs, i);
    for (pair<int, int> Q : v[i]) {
      for (int j = 0; j <= 16; j++) {
        if (ne_ans[j] >= Q.first) {
          ans[Q.second] = j;
          break;
        }
      }
    }
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
}