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$.

Input

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$.

Output

For each testcase, output the minimum cost.

Note

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.