#include <bits/stdc++.h>
using namespace std;

#define     filename "thaotac"

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
#define     nl "\n"
#define     sp " "
#define     yes "YES"
#define     no "NO"
#define     impossible "IMPOSSIBLE"

#define     pb push_back
#define     popb pop_back
#define     all(v) (v).begin(), (v).end()
#define     fi first
#define     se second
//-1 neu x = 0
#define     bit_count(x) (__builtin_popcountll(x))

#define     GCD(a,b) (__gcd((a),(b)))
#define     LCM(a,b) ((a) / __gcd((a),(b)) * (b))


#define     for_in_set(se) for(auto it = (se).begin(); it != (se).end(); ++it)
#define     rnd(l,r) ((l) + rd() % ((r) - (l) + 1))

typedef long long ll;
const int mod   = 1e9 + 7;
const int maxn  = 2e5;
const int INF   = 1e9 + 5;
const ll  LLINF = 1e18 + 5;

int n, q, f[100005][11];
ll a[100005], grid[1001][1001], prefixsum[1001][1001], modulo_table[11][11];
void read() {
    cin >> n >> q;
    for (int i = 1; i<=n; ++i) cin >> a[i];
}

void sub1() {
    for (int hihi = 0; hihi<q; ++hihi) {
        int l, r; cin >> l >> r;
        ll res = 0;
        for (int i = l; i<=r; ++i) {
            for (int j = l; j<=r; ++j) {
                res += a[i] % a[j];
            }
        }
        cout << res << nl;
    }
}
void sub3() {
    for (int i = 1; i<=n; ++i) {
        for (int j = 1; j<=n; ++j) {
            grid[i][j] = a[i] % a[j];
        }
    }

    for (int i = 1; i<=n; ++i) {
        for (int j = 1; j<=n; ++j) {
            prefixsum[i][j] = grid[i][j] + prefixsum[i-1][j] + prefixsum[i][j-1] - prefixsum[i-1][j-1];
        }
    }

    for (int i = 0; i<q; ++i) {
        int l, r; cin >> l >> r;
        int x1 = l, y1 = l, x2 = r, y2 = r;
        ll res = prefixsum[r][r] + prefixsum[l-1][l-1] - prefixsum[r][l-1] - prefixsum[l-1][r];
        cout << res << nl;
    }
}
void sub2() {
    for (int i = 1; i<=n; ++i) {
        for (int j = 1; j<=10; ++j) f[i][j] = f[i-1][j];
        ++f[i][a[i]];
    }
    for (int i = 1; i<=10; ++i) {
        for (int j = 1; j<=10; ++j) modulo_table[i][j] = i % j;
    }
    while (q--) {
        int l, r; cin >> l >> r;
        ll res = 0;
        vector <int> freq;
        freq.push_back(0);
        for (int i = 1; i<=10; ++i) freq.pb(f[r][i] - f[l-1][i]);

        for (int i = 1; i<=10; ++i) {
            for (int j = 1; j<=10; ++j) {
                res += freq[i] * freq[j] * modulo_table[i][j];
            }
        }
        cout << res << nl;
    }
}
void sub4(int maxval) {

}
void solve() {
    int g = *max_element(a+1, a+n+1);
    if (n <= 100 && q <= 100) sub1();
    else if (n <= 5e4 && q <= 1e5 && g <= 10) sub2();
    else if (n <= 1e3 && q <= 1e5 && g <= 1e5) sub3();
    else sub4(g);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    if (fopen(filename ".inp", "r")) {
        freopen(filename ".inp", "r", stdin);
        freopen(filename ".out", "w", stdout);
    }

    int t = 1;
    //cin >> t;
    while (t--) {
        read();
        solve();
        cout << nl;
    }

    return 0;
}