Untitled

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
template<class T> using orderedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
void File() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("errors.txt", "w", stderr);
#else

#endif
}
const int N = sqrt(1e9 + 16) + 16;
int main() {
    File();
    vector<bool> is_prime(N, true);
    vector<int> p;
    is_prime[0] = is_prime[1] = false;
    for (ll i = 1; i < N; ++i) {
        if (is_prime[i]) {
            p.push_back(i);
            for (ll j = i * i; j < N; j += i)
                is_prime[j] = false;
        }
    }
    int n, q;
    cin >> n >> q;
    vector<ll> a(n), com;
    for (auto &x: a) {
        cin >> x;
        for (auto &pr: p) {
            bool c = false;
            while (x % pr == 0) c ^= 1, x /= pr;
            if (c) x *= pr;
        }
        com.push_back(x);
    }
    sort(com.begin(), com.end());
    com.erase(unique(com.begin(), com.end()), com.end());
    for (auto &x: a)
        x = lower_bound(com.begin(), com.end(), x) - com.begin();
    vector<array<int, 3>> qu(q);
    for (int i = 0; i < q; ++i) {
        auto &[l, r, id] = qu[i];
        cin >> l >> r;
        --l, --r, id = i;
    }
    int sqr = 350;
    sort(qu.begin(), qu.end(), [&](array<int, 3> &i1, array<int, 3> &i2) {
        int b1 = i1[0] / sqr, b2 = i2[0] / sqr;
        return b1 == b2 ? i1[1] < i2[1] : b1 < b2;
    });
    vector<ll> frq(n), ans(q);
    ll curL = 0, curR = -1, res = 0;
    for (auto &[l, r, id]: qu) {
        while (curL > l) res += frq[a[--curL]]++;
        while (curR < r) res += frq[a[++curR]]++;
        while (curL < l) res -= --frq[a[curL++]];
        while (curR > r) res -= --frq[a[curR--]];
        ans[id] = res;
    }
    for (auto &x: ans)
        cout << x << "\n";
    return 0;
}