#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define all(p) (p).begin(),(p).end()
#include <atcoder/modint>
using mint = atcoder::modint998244353;

random_device seed_gen;
mt19937 rng(seed_gen());
// return [l, r)
long long rand_long(long long l,long long r){
    return uniform_int_distribution<long long>(l,r-1)(rng);
}


vector<mint> solve_on(int N, vector<int> A, int Q, vector<ll> a, vector<ll> b){
	const int B = 200'200;
	vector<vector<int>> table(B);
	rep(i, 2, B) if (table[i].empty()){
		ll tmp = i;
		while (tmp < B){
			for (int j = tmp; j < B; j += tmp){
				table[j].push_back(tmp);
			}
			tmp *= i;
		}
	}
    vector<vector<int>> left(N), right(N);
    vector<pair<int, int>> front(B, {-1, -1});
    rep(i, 0, N){
        int j = 0;
        for (auto x : table[A[i]]){
            if (front[x].first == -1){
                left[i].push_back(-1);
            }
            else{
                left[i].push_back(front[x].first);
                right[front[x].first][front[x].second] = i;
            }
            front[x] = {i, j};
            right[i].push_back(N);
            j++;
        }
    }
    int D = rand_long(50, 500);
    int len = (N + D - 1) / D;
    vector<mint> dp(len, 1);
    vector<vector<mint>> save;
    rep(i, 0, N) rep(j, 0, table[A[i]].size()){
        if (left[i][j] == -1){
            dp[i / D] *= table[table[A[i]][j]][0];
        }
    }
    rep(i, 0, N){
        if (i % D == 0){
            save.push_back(dp);
        }
        rep(j, 0, table[A[i]].size()){
            if (right[i][j] != N){
                dp[right[i][j] / D] *= table[table[A[i]][j]][0];
            }
        }
    }
    rep(i, 0, save.size()){
        save[i].insert(save[i].begin(), 1);
        rep(j, 0, i) save[i][j + 1] = 1;
        rep(j, 0, len) save[i][j + 1] *= save[i][j];
    }
    vector<mint> ans;
    mint F = 1;
    rep(id, 0, Q){
        mint a1 = F * a[id];
        mint b1 = F * b[id];
        int L = a1.val() % N + 1;
        int R = b1.val() % N + 1;
        // hide rule
        {
            if ((a[id] + b[id]) & 4){
                swap(L, R);
            }
            assert(L <= R);
        }
        L--;
        mint tmp = 1;

        if (L / D == R / D){
            rep(i, L, R) rep(j, 0, table[A[i]].size()){
                if (left[i][j] < L){
                    tmp *= table[table[A[i]][j]][0];
                }
            }
        }
        else{
            tmp = save[L / D + 1][R / D];
            rep(i, (R / D) * D, R) rep(j, 0, table[A[i]].size()){
                if (left[i][j] < L){
                    tmp *= table[table[A[i]][j]][0];
                }
            }
            int r = (R / D) * D;
            for (int i = (L / D + 1) * D - 1; i >= L; i--) rep(j, 0, table[A[i]].size()){
                if (r <= right[i][j]){
                    tmp *= table[table[A[i]][j]][0];
                }
            }
        }

        ans.push_back(tmp);
        F = tmp;
    }
    return ans;
}

int main(){
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];
    int Q;
    cin >> Q;
    vector<ll> a(Q), b(Q);
    rep(i, 0, Q) cin >> a[i] >> b[i];
    auto ans = solve_on(N, A, Q, a, b);
    for (auto x : ans){
        cout << x.val() << "\n";
    }
}