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.

No Cost Too Great (Hard Version)

Examples