#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e6 + 9, M = 2e7 + 9, Mod = 998244353; int fpow(int a, int b = Mod - 2, int m = Mod) { int res = 1; while (b) { if (b & 1) res = 1ll * res * a % m; a = 1ll * a * a % m, b >>= 1; } return res; } int _, n, K, a[N], l[N], r[N], Log[N]; class Hash { public: int B, M, H[N], pw[N], ip[N]; void init() { for (int i = 1; i <= n; i++) { H[i] = (1ll * H[i - 1] * B + a[i]) % M; } } int get(int l, int r) { if (l > r) return 0; return (H[r] - 1ll * H[l - 1] * pw[r - l + 1] % M + M) % M; } } H; int LCP(int l, int r, int x, int y, int K) { int lt = 0, rt = min({r - l + 1, y - x + 1, K}), mid; while (lt < rt) { mid = (lt + rt + 1) >> 1; if (H.get(l, l + mid - 1) == H.get(x, x + mid - 1)) lt = mid; else rt = mid - 1; } return lt; } int LCS(int l, int r, int x, int y, int K) { int lt = 0, rt = min({r - l + 1, y - x + 1, K}), mid; while (lt < rt) { mid = (lt + rt + 1) >> 1; if (H.get(r - mid + 1, r) == H.get(y - mid + 1, y)) lt = mid; else rt = mid - 1; } return lt; } int id[N][21]; struct DSU { int fa[M], siz[M], lt[N], rt[N], ans; void init(int nn) { for (int i = 1; i <= nn; i++) { fa[i] = i, siz[i] = 1; } ans = 1; for (int i = 1; i <= n; i++) { ans = 1ll * ans * (r[i] - l[i] + 1) % Mod; lt[i] = l[i], rt[i] = r[i]; } } int get(int x) { while (x != fa[x]) x = fa[x] = fa[fa[x]]; return x; } void merge(int x, int y, int l) { x = get(x), y = get(y); if (x != y) { if (siz[x] < siz[y]) swap(x, y); fa[y] = x, siz[x] += siz[y]; if (!l) { ans = 1ll * ans * fpow(rt[x] - lt[x] + 1) % Mod * fpow(rt[y] - lt[y] + 1) % Mod; lt[x] = max(lt[x], lt[y]), rt[x] = min(rt[x], rt[y]); if (lt[x] > rt[x]) ans = 0; else ans = 1ll * ans * (rt[x] - lt[x] + 1) % Mod; } } } } dsu; void merge(int x, int y, int l) { if (dsu.get(id[x][l]) == dsu.get(id[y][l])) return; dsu.merge(id[x][l], id[y][l], l); if (l) merge(x, y, l - 1), merge(x + (1 << (l - 1)), y + (1 << (l - 1)), l - 1); } void merge(int l, int r, int x, int y) { // cout << l << ' ' << r << ' ' << x << ' ' << y << endl; int i = Log[r - l + 1]; merge(l, x, i), merge(r - (1 << i) + 1, y - (1 << i) + 1, i); } int main() { H.B = 131, H.M = 1e9 + 9; H.pw[0] = H.ip[0] = 1; for (int i = 1; i <= 1e6; i++) { H.pw[i] = 1ll * H.pw[i - 1] * H.B % H.M; H.ip[i] = fpow(H.pw[i], H.M - 2, H.M); } for (int i = 2; i <= 1e6; i++) Log[i] = Log[i >> 1] + 1; scanf("%d", &_); while (_--) { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for (int i = 1; i <= n; i++) { scanf("%d%d", &l[i], &r[i]); } int tp = 0; for (int j = 0; (1 << j) <= n; j++) { for (int i = 1; i + (1 << j) - 1 <= n; i++) { id[i][j] = ++tp; } } H.init(), dsu.init(tp); for (K = 1; K <= (n >> 1); K++) { for (int i = K; i <= n; i += K) { int ls = LCS(1, i, 1, i + K, K), lp = LCP(i, n, i + K, n, K); // cout << i << ' ' << ls << ' ' << lp << endl; if (ls + lp - 1 >= K) { merge(i - ls + 1, i - ls + K, i - ls + K + 1, i - ls + K + K); merge(i + lp - K, i + lp - 1, i + lp, i + lp + K - 1); } } printf("%d ", dsu.ans); // cout << endl; } putchar('\n'); } fclose(stdin); fclose(stdout); return 0; }