#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e6 + 9, Mod = 998244353; int fpow(int a, int b = Mod - 2) { int res = 1; while (b) { if (b & 1) res = 1ll * res * a % Mod; a = 1ll * a * a % Mod, b >>= 1; } return res; } int _, n, a[N], l[N], r[N]; struct DSU { int fa[N], siz[N], lt[N], rt[N], ans; void init() { ans = 1; for (int i = 1; i <= n; i++) { fa[i] = i, lt[i] = l[i], rt[i] = r[i], siz[i] = 1; ans = 1ll * ans * (r[i] - l[i] + 1) % Mod; } } int get(int x) { while (x != fa[x]) x = fa[x] = fa[fa[x]]; return x; } void merge(int x, int y) { if (!ans) return; x = get(x), y = get(y); if (x == y) return; if (siz[y] > siz[x]) swap(x, y); 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]), siz[x] += siz[y], fa[y] = x; if (lt[x] > rt[x]) {ans = 0; return;} ans = 1ll * ans * (rt[x] - lt[x] + 1) % Mod; } } T; namespace Sub2 { int Main() { T.init(); for (int K = 1; (K << 1) <= n; K++) { if (!T.ans) {printf("0 "); continue;} int len = 0, lst = 0; for (int i = 1, j = K + 1; j <= n - K + 1; i++, j++) { for (int _i = i + len, _j = j + len; _i <= i + K - 1; _i++, _j++) { if (a[_i] == a[_j]) len++; else break; } if (len == K) { for (int k = max(i, lst + 1); k <= i + K - 1; k++) { T.merge(k, k + K), lst = k; } } if (len > 0) len--; } printf("%d ", T.ans); } putchar('\n'); return 0; } } int main() { 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]); } Sub2::Main(); } return 0; }