题目描述

这是该问题的困难版本。版本之间的差异在于，在此版本中， 对于所有 $i$ ( $1 \le i \le n$ )， $1 \le b_i \le 10^9$。

你有两个长度为 $n$ 的正整数数组 $a$ 和 $b$。你可以任意次（也可以 $0$ 次）对某个位置 $i$ 做如下操作：

• 将 $a_i$ 增加 $1$，这次操作的代价为 $b_i$。

问：使得存在两个下标 $i,j$（$1\le i<j\le n$）满足 $\gcd(a_i,a_j)>1$ 的最小总代价是多少？

其中 $\gcd(x,y)$ 表示 $x$ 与 $y$ 的最大公约数。

输入格式

• 第 $1$ 行：一个整数 $t$，表示测试用例的个数。

• 对于每个测试用例有三行输入：

  • 第 $1$ 行：整数 $n$（$2\le n\le 2\cdot10^5$）。
  • 第 $2$ 行：$n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le 2\cdot10^5$）。
  • 第 $3$ 行：$n$ 个整数 $b_1,b_2,\dots,b_n$（$1 \le b_i \le 10^9$）。

保证所有测试用例中 $\sum n \le 2\cdot10^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

说明

样例解释

• 第一个测试用例：初始 $a=[1,1]$。可以对第一个元素加 $1$（代价 $1$）得到 $[2,1]$，再对第二个元素加 $1$（代价 $2$）得到 $[2,2]$，此时 $\gcd(2,2)=2>1$，总代价 $3$。可以证明不可更小。
• 第二个测试用例：$a=[4,8]$，已满足 $\gcd(4,8)=4>1$，所以代价 $0$。