Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

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 a1,a2,,an and b1,b2,,bn.

You must perform the following operation exactly once:

  • choose any indices l and r such that 1lrn;
  • swap ai and bi for all i such that lir.

Find the maximum possible value of gcd(a1,a2,,an)+gcd(b1,b2,,bn) 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 (1t105), 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 (1n2105), representing the number of integers in each array.

In the next line, you are given n integers a1,a2,,an (1ai109) — the elements of the array a.

In the last line, you are given n integers b1,b2,,bn (1bi109) — the elements of the array b.

The sum of values of n over all test cases does not exceed 5105.

Output

For each test case, output a line with two integers: the maximum value of gcd(a1,a2,,an)+gcd(b1,b2,,bn) 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.