#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int MAXN = 200111;
const int MAXA = 1000 * 1000 + 1;

int lp[MAXA];
int del[MAXA];

void init(){
    vector <int> pr;
    for(int i = 2; i <= MAXA; i++){
        if(lp[i] == 0){
            lp[i] = i;
            pr.emplace_back(i);
        }

        for(int j = 0; j < pr.size() && pr[j] <= lp[i] && pr[j] * i <= MAXA; j++)
            lp[i * pr[j]] = pr[j];
    }
}

void factorize(int x){
    vector <int> fact;
    while(x != 1){
        int curp = lp[x];
        fact.emplace_back(curp);
        while(x % curp == 0)x /= curp;
    }
    int n = (1 << fact.size());
    vector <int> dp(n);
    dp[0] = 1;
    for(int mask = 1; mask < n; mask++){
        int bit = 31 - __builtin_clz(mask);
        dp[mask] = dp[mask ^ (1 << bit)] * fact[bit];
        del[dp[mask]] += 1;
    }
}

int get(int x, int n){
    vector <int> fact;
    while(x != 1){
        int curp = lp[x];
        fact.emplace_back(curp);
        while(x % curp == 0)x /= curp;
    }
    int m = (1 << fact.size());
    vector <int> dp(m);
    dp[0] = 1;
    for(int mask = 1; mask < m; mask++){
        int bit = 31 - __builtin_clz(mask);
        dp[mask] = dp[mask ^ (1 << bit)] * fact[bit];
        if(__builtin_popcount(mask) & 1) n -= del[dp[mask]];
        else n += del[dp[mask]];
    }
    return n;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector <int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    int m;
    cin >> m;
    init();
    vector < pair <int, pii> > queries(m);
    vector < set <int> > qs(n);
    map < pair <int, int> , int> ans;
    for(int i = 0; i < m; i++){
        int l, r, x;
        cin >> l >> r >> x;
        l--, r--;
        queries[i] = {x, {l, r}};
        if(l > 0)
            qs[l - 1].insert(x);
        qs[r].insert(x);
    }

    for(int i = 0; i < n; i++){
        factorize(a[i]);
        for(auto j = qs[i].begin(); j != qs[i].end(); j++)
            ans[{i, *j}] = get(*j, i + 1);
    }
    for(int i = 0; i < m; i++){
        int x = queries[i].first, l = queries[i].second.first, r = queries[i].second.second;
        cout << (l == 0 ? ans[{r, x}] : ans[{r, x}] - ans[{l - 1, x}] ) << '\n';
    }
    return 0;
}