#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 7;
const int maxm = 1e6 + 7;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const int mlog = 20;
const int SQ = 400;
int n, q;
int a[maxn], idx[maxm];
int par[maxn];
int p[maxn];
bool mark[maxm];
vector<int> divs[maxm];
set<pair<int, int> > st;
int get(int v) { return (par[v] == v ? v : par[v] = get(par[v])); }
void prep() {
  int tot = 0;
  mark[1] = true;
  for (int i = 2; i < maxm; i++) {
    if (!mark[i]) p[++tot] = i;
    for (int j = 1; j <= tot && i * p[j] < maxm; j++) {
      mark[i * p[j]] = true;
      if (i % p[j] == 0) break;
    }
  }
  for (int i = 1; i <= tot; i++)
    for (int j = p[i]; j < maxm; j += p[i]) divs[j].push_back(i);
  for (int i = 1; i < maxn; i++) par[i] = i;
}
int32_t main() {
  ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
  ;
  cin >> n >> q;
  for (int i = 1; i <= n; i++) cin >> a[i], idx[a[i]] = i;
  prep();
  for (int i = 1; i <= n; i++)
    for (int x : divs[a[i]]) par[get(i)] = get(n + x);
  for (int i = 1; i <= n; i++) {
    for (int x : divs[a[i]])
      for (int y : divs[a[i] + 1]) st.insert(make_pair(get(x + n), get(y + n)));
    for (int x : divs[a[i] + 1])
      for (int y : divs[a[i] + 1]) st.insert(make_pair(get(x + n), get(y + n)));
  }
  while (q--) {
    int s, t;
    cin >> s >> t;
    if (get(s) == get(t)) {
      cout << 0 << "\n";
      continue;
    }
    if (st.count(make_pair(get(s), get(t))) ||
        st.count(make_pair(get(t), get(s)))) {
      cout << 1 << "\n";
      continue;
    }
    cout << 2 << "\n";
  }
  return 0;
}
