#include<bits/stdc++.h>
# define rep(i, j, k) for (int i = j; i <= k; ++i)
# define N 500005
# define B 1201
using namespace std;

int fac[N], now[N], x[7000005];
basic_string < int > plc[N], big[1005];
int p[41540], cnt, len[41540];
int n, m, a[N];
int l[N], r[N], xl[N], xr[N], b[N], bl[1005], br[1005], d[N], xd[N];
long long pre[N], ans[N];
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	cin >> n >> m;
	rep(i, 1, 500000) for (int j = i; j <= 500000; j += i) ++fac[j];
	rep(i, 1, 500000) if (fac[i] == 2) p[++cnt] = i, len[cnt] = 500000 / i;
	rep(i, 1, 500000) fac[i] += fac[i - 1], now[i] = fac[i - 1] + 1;
	rep(i, 1, 500000) for (int j = i; j <= 500000; j += i) x[now[j]++] = i;
	rep(i, 1, 1000) bl[i] = 500000;
	rep(i, 1, n) b[i] = (i + 700) / B, bl[b[i]] = min(bl[b[i]], i), br[b[i]] = max(br[b[i]], i);
	rep(i, 1, n) cin >> a[i];
	rep(i, 1, m) cin >> l[i] >> r[i], plc[l[i] - 1].push_back(i), plc[r[i]].push_back(i);
	rep(i, 1, m) if (b[l[i]] < b[r[i]] - 1) big[b[l[i]]].push_back(i), big[b[r[i]] - 1].push_back(i);
	rep(i, 1, n)
	{
		rep(j, fac[a[i] - 1] + 1, fac[a[i]]) ++d[x[j]];
		for (auto j : plc[i])
		{
			int now = 0;
			if (b[l[j]] == b[r[j]]) rep(i, l[j], r[j]) now += d[a[i]];
			else {rep(k, l[j], br[b[l[j]]]) now += d[a[k]]; rep(k, bl[b[r[j]]], r[j]) now += d[a[k]];}
			ans[j] += (i == r[j] ? now : -now);
		}
	}
	rep(i, 0, b[n])
	{
	    rep(j, bl[i], br[i]) ++xd[a[j]];
	    rep(i, 1, 500000) d[i] = xd[i];
		rep(j, 1, cnt) rep(k, 1, len[j]) d[k * p[j]] += d[k];
		rep(j, 1, n) pre[j] = pre[j - 1] + d[a[j]];
		for (auto j : big[i]) ans[j] += (b[l[j]] == i ? -1 : 1) * (pre[r[j]] - pre[l[j] - 1]);
	}
	rep(i, 1, m) cout << ans[i] << '\n';
	return 0;
}