D. Alter the GCD
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_n$$$.

You must perform the following operation exactly once:

  • choose any indices $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le n$$$;
  • swap $$$a_i$$$ and $$$b_i$$$ for all $$$i$$$ such that $$$l \leq i \leq r$$$.

Find the maximum possible value of $$$\text{gcd}(a_1, a_2, \ldots, a_n) + \text{gcd}(b_1, b_2, \ldots, b_n)$$$ after performing the operation exactly once. Also find the number of distinct pairs $$$(l, r)$$$ which achieve the maximum value.

Input

In the first line of the input, you are given a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$), the number of test cases. Then the description of each test case follows.

In the first line of each test case, you are given a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), representing the number of integers in each array.

In the next line, you are given $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

In the last line, you are given $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — the elements of the array $$$b$$$.

The sum of values of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, output a line with two integers: the maximum value of $$$\text{gcd}(a_1, a_2, \ldots, a_n) + \text{gcd}(b_1, b_2, \ldots, b_n)$$$ after performing the operation exactly once, and the number of ways.

Example
Input
5
8
11 4 16 17 3 24 25 8
8 10 4 21 17 18 25 21
4
6 4 24 13
15 3 1 14
2
13 14
5 8
8
20 17 15 11 21 10 3 7
9 9 4 20 14 9 13 1
2
18 13
15 20
Output
2 36
3 2
2 3
2 36
6 1
Note

In the first, third, and fourth test cases, there's no way to achieve a higher GCD than $$$1$$$ in any of the arrays, so the answer is $$$1 + 1 = 2$$$. Any pair $$$(l, r)$$$ achieves the same result; for example, in the first test case there are $$$36$$$ such pairs.

In the last test case, you must choose $$$l = 1$$$, $$$r = 2$$$ to maximize the answer. In this case, the GCD of the first array is $$$5$$$, and the GCD of the second array is $$$1$$$, so the answer is $$$5 + 1 = 6$$$, and the number of ways is $$$1$$$.