#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int pri[N / 3], top, nxt[N];
bool is[N];
int a[N], n, q;
int f[N], ft[N];
int fa(int x) { return f[x] == x ? x : f[x] = fa(f[x]); }
vector<int> tmp;
set<pair<int, int> > dic;
int main() {
  for (int i = 2; i < N; ++i) {
    if (!is[i]) {
      pri[++top] = i;
      nxt[i] = i;
    }
    for (int j = 1; j <= top && (long long)pri[j] * i < N; ++j) {
      is[pri[j] * i] = 1;
      nxt[pri[j] * i] = pri[j];
      if (i % pri[j] == 0) break;
    }
  }
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; ++i) f[i] = i;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i);
    int now = a[i];
    while (now > 1) {
      int p = nxt[now];
      if (ft[p] == 0) ft[p] = i;
      int x = fa(i), y = fa(ft[p]);
      f[x] = y;
      now /= p;
    }
  }
  for (int i = 1; i <= n; ++i) {
    tmp.clear();
    tmp.push_back(fa(i));
    int now = a[i] + 1;
    while (now > 1) {
      int p = nxt[now];
      if (ft[p] != 0) tmp.push_back(fa(ft[p]));
      now /= p;
    }
    for (int u : tmp)
      for (int v : tmp) dic.insert(make_pair(u, v));
  }
  for (int i = 1; i <= q; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    u = fa(u), v = fa(v);
    if (u == v)
      puts("0");
    else if (dic.find(make_pair(u, v)) != dic.end())
      puts("1");
    else
      puts("2");
  }
  return 0;
}
