CF2154C2.No Cost Too Great (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, $1 \le b_i \le 10^9$ for all $i$ ($1 \le i \le n$). You can hack only if you solved all versions of this problem.

You find yourself with two arrays of positive integers $a$ and $b$, both of length $n$. You will perform the following operation any number of times (possibly none):

• select an integer $i$ ($1 \le i \le n$) and increase $a_i$ by $1$. This has a cost of $b_i$.

Determine the minimum total cost to make it so that there exists two integers $i, j$ where $1 \le i \lt j \le n$ and $\gcd(a_i, a_j)$$^{\text{∗}}$$ \gt 1$.

$^{\text{∗}}$$\gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$.

这是该问题的困难版本。两个版本的区别在于，在本版本中，对所有 $i$（$1 \le i \le n$），均有 $1 \le b_i \le 10^9$。仅当您已解决该问题的所有版本时，才可进行 hack。

您手上有两个长度均为 $n$ 的正整数数组 $a$ 和 $b$。您可以执行以下操作任意次（包括零次）：

• 选择一个整数 $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$ 的最大公约数（GCD）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each testcase contains an integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the array $a$.

The second line of each testcase contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 2 \cdot 10^5$).

The third line of each testcase contains $n$ integers $b_1,b_2,\ldots,b_n$ ($\color{red}{1 \le b_i \le 10^9}$).

The sum of $n$ across all testcases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each testcase, output the minimum cost.

对于每个测试用例，输出最小花费。

In the first testcase we can do the following: $[\color{red}1, 1] \xrightarrow{x = 1} [2, \color{red}1] \xrightarrow{x = 2} [2, 2]$, this has cost $1 + 2 = 3$. Now $\gcd(a_1, a_2) = \gcd(2, 2) = 2$ and so $\gcd(a_1, a_2) \gt 1$. It can be proven that this is the minimum cost required.

In the second testcase it is already true that $\gcd(a_1, a_2) = 4$ and so $\gcd(a_1, a_2) \gt 1$. So no operations are required.

在第一个测试用例中，我们可以执行以下操作：$[\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$，无需执行任何操作。