#include <bits/stdc++.h>
using namespace std;
const char nl = '\n';
const long long inf = 1e9 + 10;
const long long inf2 = 1e18 + 99LL;
const long double inf3 = 1e17;
const long long mod = 1e9 + 7, mod2 = 998244353;
const long double eps = 1e-9;
const bool local = false;
const int logn = 17, maxn = 1000001, maxm = 200001, maxn2 = 3;
int p[maxn], s[maxn];
int find(int v) {
  if (p[v] != v) p[v] = find(p[v]);
  return p[v];
}
void f(int a, int b) {
  a = find(a);
  b = find(b);
  if (a == b) return;
  if (s[a] < s[b]) swap(a, b);
  p[b] = a;
  s[a] += s[b];
}
vector<int> b[maxn];
int c[maxn];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  ;
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) {
    int j = 2;
    int ta = a[i];
    while (j * j <= ta) {
      if (ta % j == 0) {
        b[j].push_back(i);
        while (ta % j == 0) ta /= j;
      }
      j++;
    }
    if (ta > 1) b[ta].push_back(i);
  }
  for (int i = 0; i < n; i++) {
    s[i] = 1;
    p[i] = i;
  }
  for (int i = 0; i < maxn; i++) {
    for (int j = 0; j + 1 < (int)((b[i]).size()); j++) {
      f(b[i][j], b[i][j + 1]);
    }
  }
  for (int i = 0; i < maxn; i++) {
    if ((int)((b[i]).size())) {
      c[i] = find(b[i][0]);
    } else {
      c[i] = -1;
    }
  }
  set<pair<int, int>> st;
  for (int i = 0; i < n; i++) {
    int j = 2;
    int ta = a[i] + 1;
    vector<int> d;
    while (j * j <= ta) {
      if (ta % j == 0) {
        d.push_back(j);
        while (ta % j == 0) ta /= j;
      }
      j++;
    }
    if (ta > 1) d.push_back(ta);
    vector<int> e = {find(i)};
    for (int x : d) {
      if (c[x] == -1) continue;
      e.push_back(c[x]);
    }
    for (j = 0; j < (int)((e).size()); j++) {
      for (int k = j + 1; k < (int)((e).size()); k++) {
        int x = e[j], y = e[k];
        if (x == y) continue;
        if (x > y) swap(x, y);
        st.emplace(x, y);
      }
    }
  }
  while (q--) {
    int ts, t;
    cin >> ts >> t;
    ts--;
    t--;
    int x = find(ts), y = find(t);
    if (x > y) swap(x, y);
    if (x == y) {
      cout << 0 << nl;
    } else if (st.count({x, y})) {
      cout << 1 << nl;
    } else {
      cout << 2 << nl;
    }
  }
}
