https://ac.nowcoder.com/acm/contest/82526/D

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define oz 998244353
#define N 100010
#define INF 0x3f3f3f3f
typedef long long ll;
#define endl '\n'
const int mod = 1e9 + 7;

int f(int n) {

    int x = n;
    int res = 1;
    map<int, int> mp;

    for (int i = 2; i <= x / i; i++) {
        while (x % i == 0) {
            x /= i;
            mp[i] ++;
        }
    }

    if (x > 1)mp[x] ++;
    for (auto [u, v] : mp)res = res * (v + 1);
    return res;

}

int a[N], b[135][N];
void solve() {

    int n, q;
    cin >> n >> q;

//  for(int i = 1; i <= 10; i++)cout << f(i) << endl;



    for (int i = 1; i <= n; i ++) {
        cin >> a[i];

        int q = f(a[i]);

        for (int j = 1; j <= 130; j ++) {
            b[j][i] += b[j][i - 1];
        }
        b[q][i] ++;
    }

    while (q --) {
        int l, r;
        cin >> l >> r;

        int res = 0;

        for (int i = 1; i <= 130; i++) {
            int num = b[i][r] - b[i][l - 1];

            res += (num * (num - 1)) / 2;
        }

        cout << res << endl;

    }


}

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
//  cin >> T;
    while (T --)

        solve();

    return 0;
}