#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int par[N], ran[N];
struct DSU {
  DSU() {
    for (int i = 1; i < N; ++i) par[i] = i, ran[i] = 1;
  }
  int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
  bool unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return false;
    ran[a] += ran[a] == ran[b];
    if (ran[a] < ran[b]) swap(a, b);
    par[b] = a;
    return true;
  }
};
int a[N];
int n, q;
vector<int> primes;
int spf[N];
void sieve() {
  for (int i = 2; i < N; ++i) {
    if (spf[i] == 0) spf[i] = i, primes.push_back(i);
    int sz = primes.size();
    for (int j = 0; j < sz && i * primes[j] < N && primes[j] <= spf[i]; ++j) {
      spf[i * primes[j]] = primes[j];
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  sieve();
  cin >> n >> q;
  DSU ds;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; ++i) {
    int x = a[i];
    while (x > 1) {
      ds.unite(spf[a[i]], spf[x]);
      x /= spf[x];
    }
  }
  set<pair<int, int>> pary;
  for (int i = 1; i <= n; ++i) {
    int x = a[i];
    vector<int> v;
    while (x > 1) {
      v.push_back(spf[x]);
      x /= spf[x];
    }
    x = a[i] + 1;
    while (x > 1) {
      v.push_back(spf[x]);
      x /= spf[x];
    }
    v.resize(unique(v.begin(), v.end()) - v.begin());
    for (auto &j : v) {
      j = ds.find(j);
    }
    for (auto j : v) {
      for (auto k : v) {
        if (j < k) pary.insert({j, k});
      }
    }
  }
  while (q--) {
    int x, y;
    cin >> x >> y;
    x = spf[a[x]], y = spf[a[y]];
    if (ds.find(x) == ds.find(y))
      cout << 0 << endl;
    else {
      x = ds.find(x);
      y = ds.find(y);
      if (x > y) swap(x, y);
      if (pary.count({x, y}))
        cout << 1 << endl;
      else
        cout << 2 << endl;
    }
  }
}
