D. Alter the GCDtime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputIn 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$$$.OutputFor 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.ExampleInput5811 4 16 17 3 24 25 88 10 4 21 17 18 25 2146 4 24 1315 3 1 14213 145 8820 17 15 11 21 10 3 79 9 4 20 14 9 13 1218 1315 20Output2 36
3 2
2 3
2 36
6 1
NoteIn 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$$$.