CF1806F2 GCD Master (hard version)

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.

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