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.

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

Alter the GCD

Examples