D. 改变 GCD

每个测试点时间限制：$4$ 秒
每个测试点内存限制：$256$ MB

---

题目描述

你有两个数组 $a_1, a_2, \dots, a_n$ 和 $b_1, b_2, \dots, b_n$。

你必须恰好执行一次如下操作：

• 选择任意下标 $l$ 和 $r$，满足 $1 \le l \le r \le n$；
• 对于所有 $i$ 满足 $l \le i \le r$，交换 $a_i$ 和 $b_i$。

操作执行后，定义：

$$\text{值} = \gcd(a_1, a_2, \dots, a_n) + \gcd(b_1, b_2, \dots, b_n) $$

求这个值的最大值，以及达到这个最大值的不同 $(l, r)$ 对的数量。

---

输入

第一行一个整数 $t$（$1 \le t \le 10^5$），表示测试用例数。
接下来每个测试用例：

• 第一行一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示数组长度。
• 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。
• 第三行 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le 10^9$）。

所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。

---

输出

对于每个测试用例，输出一行两个整数：
最大值 和 达到该最大值的不同 $(l, r)$ 对的数量。

---

样例

输入：

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

输出：

2 36
3 2
2 3
2 36
6 1

---

样例解释

• 在第一个、第三个和第四个测试用例中，任何数组的 GCD 都无法大于 $1$，因此答案为 $1 + 1 = 2$。任意 $(l, r)$ 对都能达到相同结果，例如第一个测试用例有 $36$ 种这样的对。
• 在最后一个测试用例中，必须选择 $l = 1, r = 2$ 才能最大化答案。此时第一个数组的 GCD 为 $5$，第二个数组的 GCD 为 $1$，所以答案是 $5 + 1 = 6$，方案数为 $1$。

---

如果你需要这道题的解题思路或代码实现，我可以继续提供。