#P1806F2. GCD Master (hard version)
GCD Master (hard version)
Description
This is the hard version of the problem. The only difference between the two versions is the constraint on $m$. You can make hacks only if both versions of the problem are solved.
You are given an array $a$ of length $n$ and two integers $m$ and $k$. Each element in $a$ satisfies $1\le a_i \le m$.
In one operation, you choose two indices $i$ and $j$ such that $1 \le i < j \le |a|$, then append $\gcd(a_i,a_j)$ to the back of the array and delete $a_i$ and $a_j$ from the array. Note that the length of the array decreases by one after this operation.
Find the maximum possible sum of the array after performing exactly $k$ operations.
The first line contains a single integer $t$ ($1\le t\le 10^5$) — the number of test cases. The description of test cases follows.
The first line of each test case contains three integers $n$, $m$ and $k$ ($2 \le n \le 10^6$; $1\le m \le 9\cdot 10^{18}$; $1 \le k \le n-1$).
The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le m$).
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.
For each test case, output the maximum possible sum of the array after performing $k$ operations optimally.
Input
The first line contains a single integer $t$ ($1\le t\le 10^5$) — the number of test cases. The description of test cases follows.
The first line of each test case contains three integers $n$, $m$ and $k$ ($2 \le n \le 10^6$; $1\le m \le 9\cdot 10^{18}$; $1 \le k \le n-1$).
The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le m$).
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.
Output
For each test case, output the maximum possible sum of the array after performing $k$ operations optimally.
4
3 8 1
4 7 8
5 114514 2
7 2 4 1 6
3 1919810 2
2 3 3
3 9000000000000000000 1
9000000000000000000 9000000000000000000 9000000000000000000
11
14
1
18000000000000000000
Note
In the first test case, the best way is to choose $i=1$, $j=3$ in the first operation. The final sequence is $[7,4]$.