import sys
input = sys.stdin.readline
MOD = 998244353
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
a = [0] * Q
b = [0] * Q
for i in range(Q):
    a[i], b[i] = map(int, input().split())
lim = 200001
table = [[] for _ in range(lim)]
for i in range(2, lim):
    if len(table[i]) == 0:
        tmp = i
        while tmp < lim:
            j = tmp
            while j < lim:
                table[j].append(tmp)
                j += tmp
            tmp *= i

div = []
pos = []
len_sum = [0] * (N + 1)
for i in range(N):
    len_sum[i + 1] = len_sum[i]
    for x in table[A[i]]:
        div.append(x)
        pos.append(i)
        len_sum[i + 1] += 1
LS = len_sum[-1]
lef = [-1] * LS
rig = [LS] * LS
fr = [-1] * lim
for i in range(LS):
    if fr[div[i]] != -1:
        lef[i] = fr[div[i]]
        rig[fr[div[i]]] = i
    fr[div[i]] = i
D = 100
ND = (N + D - 1) // D
dp = [1] * (ND + 1)
save = []
ind = 0
for i in range(LS):
    if lef[i] == -1:
        x = pos[i] // D + 1
        dp[x] = dp[x] * table[div[i]][0] % MOD
while ind < N:
    n_ind = min(ind + D, N)
    th = ind // D
    for j in range(0, ND + 1):
        if j <= th:
            save.append(1)
        else:
            save.append(save[-1] * dp[j] % MOD)
    for i in range(len_sum[ind], len_sum[n_ind]):
        if rig[i] != LS:
            x = pos[rig[i]] // D + 1
            dp[x] = dp[x] * table[div[i]][0] % MOD
    ind = n_ind
ans = 1
for rp in range(Q):
    L = ans * a[rp] % MOD
    R = ans * b[rp] % MOD
    L %= N
    R %= N
    if L > R:
        L, R = R, L
    R += 1
    ans = 1
    if L // D == R // D:
        for i in range(len_sum[L], len_sum[R]):
            if len_sum[R] <= rig[i]:
                ans = ans * table[div[i]][0] % MOD
    else:
        ans = save[(ND + 1) * (L // D + 1) + R // D]
        l = len_sum[(L // D + 1) * D]
        for i in range(len_sum[(R // D) * D], len_sum[R]):
            if lef[i] < l:
                ans = ans * table[div[i]][0] % MOD
        r = len_sum[R]
        for i in range(len_sum[L], len_sum[(L // D) * D + D]):
            if r <= rig[i]:
                ans = ans * table[div[i]][0] % MOD
    print(ans, flush=False)