#include <bits/stdc++.h>
using namespace std;
const long long max_n = 1000006;
inline long long read() {
  long long x = 0;
  bool w = 0;
  char c = getchar();
  while (c < '0' || c > '9') w |= c == '-', c = getchar();
  while (c >= '0' && c <= '9')
    x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return w ? -x : x;
}
inline void write(long long x) {
  if (x < 0) x = -x, putchar('-');
  if (x > 9) write(x / 10);
  putchar(x % 10 ^ 48);
}
long long n, a[max_n], t[max_n], pr[max_n];
struct unionfind {
  long long fa[max_n], sz[max_n];
  inline void clear() {
    for (register long long i = 0; i <= n; ++i) fa[i] = i;
  }
  inline long long find(long long x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
  }
  inline void merge(long long x, long long y) {
    x = find(x), y = find(y);
    if (x == y) return;
    fa[x] = y;
  }
} uf;
long long c[max_n], d[max_n];
inline void getpr() {
  for (register long long i = 2; i < max_n; ++i)
    if (!pr[i])
      for (register long long j = i, k = 0; j < max_n; j += i) {
        if (t[j]) {
          if (!k)
            c[i] = uf.find(t[j]);
          else
            uf.merge(k, t[j]);
          k = t[j];
        }
        pr[j] = i;
      }
}
map<pair<long long, long long>, bool> mp;
signed main() {
  n = read();
  long long T = read();
  uf.clear();
  for (register long long i = 1; i <= n; ++i) {
    a[i] = read();
    t[a[i]] = i;
  }
  getpr();
  for (register long long i = 2; i < max_n; ++i)
    if (pr[i] == i) c[i] = uf.find(c[i]);
  for (register long long i = 1; i <= n; ++i) {
    long long j = a[i] + 1, cnt = 0;
    d[++cnt] = uf.find(i);
    while (j != 1) {
      d[++cnt] = c[pr[j]];
      j /= pr[j];
    }
    sort(d + 1, d + 1 + cnt), cnt = unique(d + 1, d + 1 + cnt) - d - 1;
    for (register long long j = 1; j < cnt; ++j)
      for (register long long k = j + 1; k <= cnt; ++k)
        mp[make_pair(d[j], d[k])] = 1;
  }
  while (T--) {
    long long x = read(), y = read();
    x = uf.find(x), y = uf.find(y);
    if (x == y) {
      puts("0");
      continue;
    }
    if (x > y) x ^= y ^= x ^= y;
    if (mp[make_pair(x, y)])
      puts("1");
    else
      puts("2");
  }
  return 0;
}
