J. Journey on the Number Line
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given $$$n$$$ points on a one-dimensional coordinate system, the coordinates of the $$$i$$$-th point are $$$x_i$$$ and the weights are $$$v_i$$$.The $$$n$$$ points are numbered $$$1$$$ through $$$n$$$ in the order of the sample inputs. Define $$$f(i,j)$$$ as the cost of traveling from the $$$i$$$-th point to the $$$j$$$-th point.

$$$f(i,j)=\left\{ \begin{matrix} x_i-x_j+v_i-v_j~,&x_i \gt x_j \\ x_j-x_i+v_j-v_i~,&x_i \lt x_j \end{matrix} \right. $$$

You need to visit all the points exactly once, starting at point $$$1$$$ and ending at point $$$n$$$. You need to answer the minimum total cost of all access sequences, and how many different access sequences can achieve this cost.

The number of legal access sequences may be large, so output the number of legal access sequences modulo $$$998244353$$$.

Input

Each test contains multiple test cases. The first line contains a single integer $$$t~(1\leq{t}\leq{5\cdot 10^3})$$$—the number of test cases. The description of the test cases follows.

Each test case consists of three lines.

The first line of each test case contains a single integer $$$n~(2\leq{n}\leq{5\cdot 10^3})$$$.

The second line of each test case contains $$$n$$$ distinct integers $$$x_1,x_2,...,x_n~(1\leq{x_i}\leq{10^9})$$$.

The third line of each test case contains $$$n$$$ integers $$$v_1,v_2,...,v_n~(1\leq{v_i}\leq{10^9})$$$.

It is guaranteed that the sum of the values of $$$n$$$ for all sets of input data does not exceed $$$5\cdot 10^3$$$.

Output

For each test case, output the minimum total cost of all access sequences, and how many different access sequences can achieve this cost.

Example
Input
3
5
1 2 3 4 5
7 2 3 5 1
5
5 3 4 1 2
7 8 6 5 7
10
75 52 80 73 77 34 96 15 16 24
4 10 13 35 10 19 87 34 93 41
Output
-2 1
7 1
78 16