#include <bits/stdc++.h>
using namespace std;
long long power(long long a, long long b, long long md) {
  return (!b ? 1
             : (b & 1 ? a * power(a * a % md, b / 2, md) % md
                      : power(a * a % md, b / 2, md) % md));
}
const int xn = 1e6 + 10;
const int xm = 2e5 + 7;
const int sq = 220;
const int inf = 1e9 + 10;
const long long INF = 1e18 + 10;
const int mod = 1e9 + 7, mod2 = 998244353;
const int LOG = 11;
int n, q, num[xn], com[xn], par[xn], sz[xn], b[xn], p[xn];
vector<int> adj[xn];
unordered_map<int, int> mp[xm];
int Parent(int v) {
  if (v == par[v]) return v;
  return par[v] = Parent(par[v]);
}
void merge(int v, int u) {
  v = Parent(v);
  u = Parent(u);
  if (v == u) return;
  par[u] = v;
  sz[v] += sz[u];
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n >> q;
  for (int i = 1; i <= n; ++i)
    cin >> num[i], par[i] = i, sz[i] = 1, com[num[i]] = i;
  for (int i = 2; i < xn; ++i) {
    int last = -1;
    for (int j = i; j < xn; j += i) {
      if (last != -1 && com[j]) merge(last, com[j]);
      if (com[j]) last = com[j];
      if (i < j) p[j] = 1;
      if (!p[i]) adj[j].push_back(i);
    }
  }
  for (int i = 1; i <= n; ++i) {
    int root = Parent(i);
    for (int v : adj[num[i]]) b[v] = root;
  }
  for (int i = 1; i <= n; ++i) {
    int root = Parent(i);
    for (int j = 0; j < int(adj[num[i] + 1].size()); ++j) {
      int v = adj[num[i] + 1][j];
      if (!b[v]) continue;
      v = b[v];
      mp[v][root] = 1;
      for (int k = 0; k < j; ++k) {
        int u = adj[num[i] + 1][k];
        if (!b[u]) continue;
        u = b[u];
        v = Parent(v);
        u = Parent(u);
        mp[v][u] = true;
      }
    }
  }
  while (q--) {
    int s, t;
    cin >> s >> t;
    s = Parent(s);
    t = Parent(t);
    if (s == t)
      cout << 0 << '\n';
    else if (mp[s][t] || mp[t][s])
      cout << 1 << '\n';
    else
      cout << 2 << '\n';
  }
  return 0;
}
