C2. Любой ценой (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии $$$1 \le b_i \le 10^9$$$ для всех $$$i$$$ ($$$1 \le i \le n$$$). Вы можете делать взломы только в том случае, если решили все версии этой задачи.

У вас есть два массива целых положительных чисел $$$a$$$ и $$$b$$$, оба длины $$$n$$$. Вы можете выполнить следующую операцию любое количество раз (возможно, ни разу):

  • выберите целое число $$$i$$$ ($$$1 \le i \le n$$$) и увеличьте $$$a_i$$$ на $$$1$$$. Это стоит $$$b_i$$$.

Определите минимальную суммарную стоимость операций, чтобы существовали два целых числа $$$i, j$$$, где $$$1 \le i \lt j \le n$$$ и $$$\gcd(a_i, a_j)$$$$$$^{\text{∗}}$$$$$$ \gt 1$$$.

$$$^{\text{∗}}$$$$$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$).

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1,b_2,\ldots,b_n$$$ ($$$\color{red}{1 \le b_i \le 10^9}$$$).

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

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

Для каждого набора входных данных выведите минимальную стоимость.

Пример
Входные данные
6
2
1 1
1 2
2
4 8
41 67
5
1 1 727 1 1
1 1 1000 1 1
2
3 11
1 1
3
2 7 11
1 6 6
3
2 7 11
100 1 2
Выходные данные
3
0
2
1
5
1
Примечание

В первом наборе входных данных мы можем сделать следующее: $$$[\color{red}1, 1] \xrightarrow{x = 1} [2, \color{red}1] \xrightarrow{x = 2} [2, 2]$$$, стоимость операций равна $$$1 + 2 = 3$$$. Теперь $$$\gcd(a_1, a_2) = \gcd(2, 2) = 2$$$, и поэтому $$$\gcd(a_1, a_2) \gt 1$$$. Можно доказать, что это минимальная необходимая стоимость.

Во втором наборе входных данных уже верно, что $$$\gcd(a_1, a_2) = 4$$$, и поэтому $$$\gcd(a_1, a_2) \gt 1$$$. Таким образом, операции не требуются.