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.

见题面 Input 部分

见题面 Output 部分

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$.