B'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 <= a_i <= m . In one operation, you choose two indices i and j such that 1 <= i < j <= |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 <= t <= 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 <= n <= 10^6 ; 1 <= m <= 9 cdot 10^{18} ; 1 <= k <= n-1 ). The second line of each test case contains n integers a_1,a_2, ldots,a_n ( 1 <= a_i <= 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] . '...