You are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$, satisfying $$$a_1 = -1,\, b_1 = -1,\, 1 \le a_i \lt i,\;1 \le b_i \lt i$$$ (for all $$$2\le i\le n$$$).
For any integer $$$x\ge1$$$, let $$$\mathrm{count}_a(x)$$$ be the number of integer arrays $$$A$$$ of length $$$n$$$ where $$$1 \le A_i \le x$$$ for all $$$i$$$, and $$$A_i \le A_{a_i}$$$ is satisfied for all $$$i \gt 1$$$.
Similarly, let $$$\mathrm{count}_b(x)$$$ be the number of integer arrays $$$B$$$ of length $$$n$$$ where $$$1 \le B_i \le x$$$ for all $$$i$$$, and $$$B_i \le B_{b_i}$$$ is satisfied for all $$$i \gt 1$$$.
It can be shown that, as $$$x$$$ approaches infinity, the ratio $$$\frac{\mathrm{count}_a(x)}{\mathrm{count}_b(x)}$$$ approaches a rational number $$$r$$$. That is, $$$$$$ r \;=\;\lim_{x\to\infty}\frac{\mathrm{count}_a(x)}{\mathrm{count}_b(x)} $$$$$$ exists and is a rational number. So $$$r$$$ can be represented as $$$\frac{p}{q}$$$ where $$$p$$$ and $$$q$$$ are coprime integers. Compute $$$p\cdot q^{-1} \;\bmod\; 998\,244\,353$$$, where $$$q^{-1}$$$ denotes the multiplicative inverse of $$$q$$$ modulo $$$998\,244\,353$$$. It is guaranteed that $$$q^{-1}$$$ exists modulo $$$998\,244\,353$$$ under the given constraints.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 3\cdot10^5$$$).
The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$a_1=-1$$$, and $$$1\le a_i \lt i$$$ for all $$$i \gt 1$$$).
The third line contains $$$n$$$ integers $$$b_1,b_2,\dots,b_n$$$ ($$$b_1=-1$$$, and $$$1\le b_i \lt i$$$ for all $$$i \gt 1$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3\cdot10^5$$$.
For each test case, output an integer — the answer modulo $$$998\,244\,353$$$.
23-1 1 1-1 1 24-1 1 1 2-1 1 2 1
2 1
Consider the first test case. For array $$$a$$$, the constraints are $$$A_2 \leq A_1$$$ and $$$A_3 \leq A_1$$$. For each value of $$$A_1 = k$$$ (where $$$1 \leq k \leq x$$$), both $$$A_2$$$ and $$$A_3$$$ can be any value from $$$1$$$ to $$$k$$$, giving $$$k^2$$$ possibilities for each $$$k$$$. Summing over all possible values of $$$k$$$ gives $$$\mathrm{count}_a(x) = \frac{x(x+1)(2x+1)}{6}$$$.
For array $$$b$$$, the constraints are $$$B_2 \leq B_1$$$ and $$$B_3 \leq B_2$$$, forming a descending chain. This gives $$$\mathrm{count}_b(x) = \frac{x(x+1)(x+2)}{6}$$$.
As $$$x$$$ tends to infinity, their ratio $$$\frac{\mathrm{count}_a(x)}{\mathrm{count}_b(x)} = \frac{2x+1}{x+2}$$$ approaches $$$2$$$.
