include <bits/stdc++.h>

using namespace std;

define int long long

const int MAXN = 1e5 + 7;

int t, n, q, k, l, r, x; map<int, set<int>> cnt; int num[MAXN];

void solve() { cin >> n >> q; cnt.clear();

for(int i = 0; i < n; i++) {
    cin >> num[i];

    cnt[num[i]].insert(i + 1);
}

while(q--) {
    cin >> k >> l >> r;

    int lastchange = l;
    int ans = 0;
    while(lastchange <= r) {
        int i = r + 1;
        for(int d = 1; d <= sqrt(k) + 1; d++) {
            if(k % d == 0) {
                int ad = d;
                int bd = k / d;

                if(cnt[ad].size() != 0) {
                    auto ii = (cnt[ad].lower_bound(lastchange));
                    if(ii != cnt[ad].end()) {
                        i = min(i, *ii);
                    }
                }

                if(cnt[bd].size() != 0) {
                    auto ii = (cnt[bd].lower_bound(lastchange));
                    if(ii != cnt[bd].end()) {
                        i = min(i, *ii);
                    }
                }
            }
        }

        ans += k * (i - lastchange);
        lastchange = i;
        if(i <= r) {
            while(k % num[i - 1] == 0)
                k /= num[i - 1];
        }
    }

    cout << ans << '\n';
}

}

signed main() { cin >> t;

while(t--) {
    solve();
}

}