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)