G. Sakura Adachi and Optimal Sequences
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
"What a pain..."
— Hougetsu Shimamura

Adachi is in the middle of a generational crashout... over, uh, this problem! Yep, that's definitely it... anyways, please help her solve it!

You are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$ ($$$1\leq a_i\leq b_i$$$).

In one operation, you may either:

  • choose an index $$$i$$$ ($$$1\leq i\leq n$$$) and set $$$a_i := a_i + 1$$$, or
  • double all elements of $$$a$$$.

Let $$$x$$$ denote the minimum number of operations needed to make $$$a = b$$$. Two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$ are considered equal if $$$a_i = b_i$$$ for all $$$1\leq i\leq n$$$.

Find the value of $$$x$$$. Additionally, count the number of sequences of operations that make $$$a = b$$$ using exactly $$$x$$$ operations. Two such sequences of operations are considered different if, for any $$$1\leq j\leq x$$$, the $$$j$$$-th operation of each sequence differs (either in the type of operation selected or the index chosen, if applicable).

Since the number of sequences may be large, output it modulo $$${\color{red}{10^6+3}}$$$. Note that $$$10^6+3$$$ is a prime number.

Input

The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 10^4$$$)  — the number of test cases.

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

The second line of each test case contains $$$n$$$ integers, $$$a_1, a_2, \dots, a_n$$$ ($$$1\leq a_i\leq 10^6$$$).

The third line of each test case contains $$$n$$$ integers, $$$b_1, b_2, \dots, b_n$$$ ($$$a_i\leq b_i\leq 10^6$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output two integers, the value of $$$x$$$, and the number of sequences of operations that make $$$a = b$$$ using exactly $$$x$$$ operations, modulo $$$10^6+3$$$. The value of $$$x$$$ should be printed exactly; that is, it should not be taken modulo $$$10^6 + 3$$$.

Example
Input
8
6
1 3 6 4 3 2
3 7 10 4 4 8
2
1 1
4 3
5
2 3 2 5 1
18 13 10 30 7
5
5 4 3 6 2
100 125 231 113 107
4
2 2 2 2
2 2 2 2
4
1 1 1 1
2 2 2 2
7
1 1 1 1 1 1 200000
200000 200000 200000 200000 200000 200000 200000
3
542264 174876 441510
641112 325241 995342
Output
17 827116
3 1
12 288
35 567812
0 1
1 1
1199994 0
803045 366998
Note

In the second sample, it is possible to convert $$$a$$$ into $$$b$$$ using only three operations. There is only one way to do so, namely:

  • Add $$$1$$$ to $$$a_1$$$, yielding $$$a = [2, 1]$$$. Then double all elements of $$$a$$$, yielding $$$a = [4, 2]$$$. Then add $$$1$$$ to $$$a_2$$$, yielding $$$a = [4, 3]$$$. Then we have that $$$a = b$$$, as desired.

It can be shown that it is impossible to convert $$$a$$$ into $$$b$$$ using fewer than three operations.