#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N = 1e6 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

struct SegmentTree {

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

    int a[N << ];

    void build(int *b, int l, int r, int rt) {

        if(l == r) {

            a[rt] = b[l];

            return;

        }

        int mid = l + r >> ;

        build(b, lson); build(b, rson);

        a[rt] = 1ll * a[rt << ] * a[rt <<  | ] % mod;

    }

    void update(int p, int val, int l, int r, int rt) {

        if(l == r) {

            a[rt] = 1ll * a[rt] * val % mod;

            return;

        }

        int mid = l + r >> ;

        if(p <= mid) update(p, val, lson);

        else update(p, val, rson);

        a[rt] = 1ll * a[rt << ] * a[rt <<  | ] % mod;

    }

    int query(int L, int R, int l, int r, int rt) {

        if(l >= L && r <= R) return a[rt];

        int mid = l + r >> ;

        if(R <= mid) return query(L, R, lson);

        else if(L > mid) return query(L, R, rson);

        else return (1ll * query(L, R, lson) * query(L, R, rson)) % mod;

    }

};

int n, q, a[N], mul[N], del[N], ans[N], Map[N];

vector<int> prime;

vector<int> fac[N];

vector<PII> qus[N];

SegmentTree seg;

int Power(int a, int b) {

    int ans = ;

    while(b) {

        if(b & ) ans = 1ll * ans * a % mod;

        a = 1ll * a * a % mod; b >>= ;

    }

    return ans;

}

int main() {

    for(int i = ; i < N; i++) {

        if(SZ(fac[i])) continue;

        prime.push_back(i);

        for(int j = i; j < N; j += i)

            fac[j].push_back(i);

    }

    for(auto& x : prime) {

        mul[x] = ( - Power(x, mod - ) + mod) % mod;

        del[x] = Power(mul[x], mod - );

    }

    scanf("%d", &n);

    for(int i = ; i <= n; i++) scanf("%d", &a[i]);

    seg.build(a, , n, );

    scanf("%d", &q);

    for(int i = ; i <= q; i++) {

        int L, R; scanf("%d%d", &L, &R);

        qus[L].push_back(mk(R, i));

    }

    for(int i = n; i >= ; i--) {

        for(auto& t : fac[a[i]]) {

            if(Map[t]) seg.update(Map[t], del[t], , n, );

            seg.update(i, mul[t], , n, );

            Map[t] = i;

        }

        for(auto& t : qus[i]) {

            ans[t.se] = seg.query(i, t.fi, , n, );

        }

    }

    for(int i = ; i <= q; i++) printf("%d\n", ans[i]);

    return ;

}

/*

*/