D. Измените НОД
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два массива $$$a_1, a_2, \ldots, a_n$$$ и $$$b_1, b_2, \ldots, b_n$$$.

Вы должны выполнить следующую операцию ровно один раз:

  • выбрать любые индексы $$$l$$$ и $$$r$$$ такие, что $$$1 \le l \le r \le n$$$;
  • поменять местами $$$a_i$$$ и $$$b_i$$$ для всех $$$i$$$ таких, что $$$l \leq i \leq r$$$.

Найдите максимально возможное значение $$$\text{gcd}(a_1, a_2, \ldots, a_n) + \text{gcd}(b_1, b_2, \ldots, 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, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

В последней строке даны $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — элементы массива $$$b$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите два целых числа: максимальное значение $$$\text{gcd}(a_1, a_2, \ldots, a_n) + \text{gcd}(b_1, b_2, \ldots, b_n)$$$ после выполнения операции ровно один раз, и количество подходящих пар.

Пример
Входные данные
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
Примечание

В первом, третьем и четвертом наборах входных данных ни в одном из массивов нельзя получить НОД больше $$$1$$$, поэтому ответ — $$$1 + 1 = 2$$$. Любая пара $$$(l, r)$$$ достигает одинаковый результат, например, в первом примере $$$36$$$ такиз пар.

В последнем наборе входных данных нужно выбрать $$$l = 1$$$, $$$r = 2$$$ для максимизации ответа. В этом случае НОД в первом массиве будет$$$5$$$, а во втором — $$$1$$$, поэтому ответ равен $$$5 + 1 = 6$$$, а количество пар равно $$$1$$$.