Zhily developed a game called Barknights, and she is preparing to release a major update on March $$$25$$$. Specifically, she plans to add a Module to each Operator in the game, multiplying their power level by the Module's power.

After the update is released, the famous game streamer Jily will evaluate the Operators' power levels and rank them in a tier list. Whenever an earlier-released Operator is ranked higher than a later-released Operator, it will cause a wave of drama.

Unfortunately, Zhily accidentally knocked over a hot water kettle and broke her computer, which caused all the Modules to be randomly rearranged. Now Zhily wants to know the expected number of waves of drama that will be generated, but since she has to move on to the next problem, she has entrusted this task to you.

You are given two arrays $$$a$$$ and $$$b$$$ of $$$n$$$ positive integers. Let $$$b'$$$ be a permutation of array $$$b$$$ chosen uniformly at random among all $$$n!$$$ possible permutations. Define $$$ c_i = a_i \cdot b'_i$$$ for $$$1\le i \le n$$$.

Find the expected number of inversions$$$^{\text{∗}}$$$ of array $$$c$$$.

$$$^{\text{∗}}$$$An inversion in array $$$c$$$ is a pair of indices $$$(i, j)$$$ such that $$$1 \le i \lt j \le n$$$ and $$$c_i \gt c_j$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$) — the length of the arrays $$$a$$$ and $$$b$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — the array $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

Output

For each test case, output the expected number of inversions in $$$c$$$ modulo $$$998\,244\,353$$$.

Formally, let $$$M = 998\,244\,353$$$. It can be shown that the exact answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Note

In the first test case, since all elements of $$$b$$$ are $$$1$$$, any of the $$$5!$$$ permutations results in $$$b' = (1, 1, 1, 1, 1)$$$. Thus, $$$c = (1, 14, 5, 1, 4)$$$ is always constant. The inversions are $$$(2, 3), (2, 4), (2, 5), (3, 4),$$$ and $$$(3, 5)$$$. The expected number of inversions is $$$5 \equiv 5 \pmod{998\,244\,353}$$$.

In the second test case, there are $$$3! = 6$$$ equally likely permutations $$$b'$$$. The resulting arrays $$$c$$$ and their respective inversion counts are shown below:

$$$b'$$$	$$$c = (3b'_1, 2b'_2, 5b'_3)$$$	Inversion Count
$$$(3, 2, 5)$$$	$$$(9, 4, 25)$$$	1
$$$(3, 5, 2)$$$	$$$(9, 10, 10)$$$	0
$$$(2, 3, 5)$$$	$$$(6, 6, 25)$$$	0
$$$(2, 5, 3)$$$	$$$(6, 10, 15)$$$	0
$$$(5, 3, 2)$$$	$$$(15, 6, 10)$$$	2
$$$(5, 2, 3)$$$	$$$(15, 4, 15)$$$	1

The expected number of inversions is $$$\frac{1+0+0+0+2+1}{6} = \frac{4}{6} = \frac{2}{3}$$$.

Modulo $$$998\,244\,353$$$, the answer is $$$2 \cdot 3^{-1} \equiv 665\,496\,236 \pmod{998\,244\,353}$$$.

Idx	Name	Rating
A	Zhily and Bracket Swapping	1300
B	Zhily and Barknights	1600
C	Zhily and Signpost	2300
D	Zhily and Cycle	2800
E	Zhily and Permutation	3500
F	Zhily and Colorful Strings	3400

Codeforces Round 1097 (Div. 1, Based on Zhili Cup 2026)