#include <bits/stdc++.h>using namespace std;const int N = 200005;/***素数打表***/int p[N];int is_p[N+1];int cnt_p;void get_p() {    for (int i = 0; i <= N; ++i) is_p[i] = 1;    cnt_p = is_p[0] = is_p[1] = 0;    for (int i = 2; i <= N; ++i) {        if (is_p[i]) {            p[cnt_p++] = i;            for (int j = i * 2; j <= N; j += i) is_p[j] = 0;        }    }}/***因数分解***/int fac[N];     // 记录出现的因数int cal_fac(int x) {    int tmp = x;    int idx = 0;    int i;    for (i = 0; p[i] <= tmp/p[i]; ++i) {        if (tmp%p[i]) continue;        while (tmp%p[i] == 0) tmp /= p[i];        fac[idx++] = p[i];    }    if (tmp != 1) fac[idx++] = tmp;    return idx;}/***计算每个数互质的最左最右区间***/int l[N], r[N];int adj[N];int a[N];void cal_inv(int n) {    for (int i = 0; i < N; ++i) adj[i] = 0;    for (int i = 1; i <= n; ++i) {        int cnt = cal_fac(a[i]);        l[i] = 0;        for (int j = 0; j < cnt; ++j) {            l[i] = max(l[i], adj[fac[j]]);            adj[fac[j]] = i;        }    }    for (int i = 0; i < N; ++i) adj[i] = n+1;    for (int i = n; i >= 1; --i) {        r[i] = n+1;        int cnt = cal_fac(a[i]);        for (int j = 0; j < cnt; ++j) {            r[i] = min(r[i], adj[fac[j]]);            adj[fac[j]] = i;        }    }}struct node {    int l, r, id;    bool operator<(const node x) const { return l < x.l; }} qry[N];int bit[N];int lowbit(int x) { return x&-x; }void add(int x, int v, int n) { while(x<=n) bit[x]+=v,x+=lowbit(x); }int sum(int x) { int ans=0; while(x) ans+=bit[x],x-=lowbit(x); return ans; }vector<int> lb[N]; // lb[i] 以i为左边界的数int ans[N];int main() {//freopen("in.txt", "r", stdin);    get_p();    int n, k;    while (~scanf("%d%d", &n, &k)) {        if (n == 0) break;        for (int i = 1; i <= n; ++i) {            scanf("%d", a+i);        }        cal_inv(n);        for (int i = 0; i < k; ++i) {            scanf("%d%d", &qry[i].l, &qry[i].r);            qry[i].id = i;        }        sort(qry, qry+k);        for (int i = 0; i <= n; ++i) lb[i].clear();        memset(bit, 0, sizeof bit);        for (int i = 1; i <= n; ++i) {            if (!l[i]) { add(i, 1, n); add(r[i], -1, n); }            else lb[l[i]].push_back(i);        }        int pos = 1;        for (int i = 0; i < k; ++i) {            while (qry[i].l > pos) {                add(pos, -1, n);                add(r[pos], 1, n);                for (unsigned j = 0; j < lb[pos].size(); ++j) {                    int x = lb[pos][j];                    add(x, 1, n);                    add(r[x], -1, n);                }                pos++;            }            ans[qry[i].id] = sum(qry[i].r)-sum(qry[i].l-1);        }        for (int i = 0; i < k; ++i) {            printf("%d\n", ans[i]);        }    }    return 0;}