#include <cctype>
#include <cstdio>

struct IO {
  static const int BUFSIZE = 1 << 20;
  char buf[BUFSIZE], *p1, *p2;
  char pbuf[BUFSIZE], *pp;
  IO() : p1(buf), p2(buf), pp(pbuf) {}
  ~IO() {
    fwrite(pbuf, 1, pp - pbuf, stdout);
  }
  
  char getchar() {
    if (p1 == p2) {
      p2 = (p1 = buf) + fread(buf, 1, BUFSIZE, stdin);
      if (p1 == p2) {
        return EOF;
      }
    }
    return *p1++;
  }
  
  void putchar(char ch) {
    if (pp - pbuf == BUFSIZE) {
      fwrite(pbuf, 1, BUFSIZE, stdout);
      pp = pbuf;
    }
    *pp++ = ch;
  } 
  
  template <typename T> T read() {
    T res = 0, f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
    return res * f;
  }
  
  void write(__int128 x, char ed) {
    int sta[64], top = 0;
    do {
      sta[++top] = x % 10;
      x /= 10;
    } while (x);
    while (top) {
      putchar(sta[top--] ^ 48);
    }
    putchar(ed);
  }
  
  template <typename T> void write(T x, char ed = '\n') {
    write((__int128)x, ed);
  }
} io;

int n, m;
int a[2000], ans[2000][2000];

bool isPrime(int x) {
  if (x <= 1) return false;
  for (int i = 2; i * i <= x; ++i) {
    if (x % i == 0) return false;
  }
  return true;
}

int main() {
  freopen("Jelly.in", "r", stdin);
  freopen("Jelly.out", "w", stdout);
  n = io.read<int>(), m = io.read<int>();
  for (int i = 1; i <= n; ++i) {
    a[i] = io.read<int>();
  }
  
  for (int i = 1; i <= n; ++i) {
    if (isPrime(a[i])) ans[i][i] = 1;
  }
  for (int len = 2; len <= n; ++len) {
    for (int l = 1; l <= n - len + 1; ++l) {
      int r = l + len - 1;
      ans[l][r] = ans[l][r - 1] + ans[l + 1][r] - ans[l + 1][r - 1];
      int check = 0;
      for (int i = l; i <= r; ++i) check |= a[i];
      ans[l][r] += isPrime(check);
    }
  }
  
  while (m--) {
    int l = io.read<int>(), r = io.read<int>();
    io.write(ans[l][r]);
  }
  return 0;
}