#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

typedef vector<ll> vl;
typedef pair<ll, ll> pll;

#define St first
#define Nd second
#define Pb push_back
#define print_pair(p) "{" << (p).St << ", " << (p).Nd << "} "
#define list_format(i, n) (i!=n? " ":"\n")
#define endl "\n"
#define sz(a) (int)a.size()

#define REP(i,a,b) for(int i = a; i <= b; i++)
#define REV(i,a,b) for(int i = a; i >= b; i--)

#define AritSum(a,d,n) ((n)*(2*(a)+((n)-1)*(d)))/2
#define Log(base, num) log2(num)/log2(base)

#define MOD 1000000007
#define INF 1e18

// ******************** Add-on *****************************

// ******************** Add-on *****************************

// ************* MAIN *******************

int A[100000];
int n, x;

void solve() {
    cin >> n >> x;
    REP(i,0,n-1) cin >> A[i];
    int it = 0;
    bool working = true;
    ll sum = accumulate(A, A + n, 0ll);
    while (working) {
        REP(i,0,n-1) {
            if (!working) break;
            if (A[i]%x == 0) sum += (ll)A[i] * (ll)pow(x, it), A[i] /= x;
            else working = false;
        }
        it++;
    }
    cout << sum << endl;
}

/*
g++ -std=c++14 -Wall -Wextra -O2 Test.cpp -o Test
./Test < in.txt

*/
int main() {    
    int _=1;
    cin>>_;
    REP(t,1,_) {
        // cout << "Case #" << t << ": ";
        solve();
        // cout << ((solve())? "YES" : "NO") << endl;
    }
    return 0;
}
### Prompt

Please formulate a cpp solution to the following problem:

You have given an array a of length n and an integer x to a brand new robot. What the robot does is the following: it iterates over the elements of the array, let the current element be q. If q is divisible by x, the robot adds x copies of the integer q/x to the end of the array, and moves on to the next element. Note that the newly added elements could be processed by the robot later. Otherwise, if q is not divisible by x, the robot shuts down.

Please determine the sum of all values of the array at the end of the process.

Input

The first input line contains a single integer t (1 ≤ t ≤ 100) — the number of test cases.

The first line of each test case contains two integers n and x (1 ≤ n ≤ 10^5, 2 ≤ x ≤ 10^9) — the length of the array and the value which is used by the robot.

The next line contains integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — the initial values in the array.

It is guaranteed that the sum of values n over all test cases does not exceed 10^5.

Output

For each test case output one integer — the sum of all elements at the end of the process.

Example

Input


2
1 2
12
4 2
4 6 8 2


Output


36
44

Note

In the first test case the array initially consists of a single element [12], and x=2. After the robot processes the first element, the array becomes [12, 6, 6]. Then the robot processes the second element, and the array becomes [12, 6, 6, 3, 3]. After the robot processes the next element, the array becomes [12, 6, 6, 3, 3, 3, 3], and then the robot shuts down, since it encounters an element that is not divisible by x = 2. The sum of the elements in the resulting array is equal to 36.

In the second test case the array initially contains integers [4, 6, 8, 2], and x=2. The resulting array in this case looks like  [4, 6, 8, 2, 2, 2, 3, 3, 4, 4, 1, 1, 1, 1, 1, 1].

### Response

```cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

typedef vector<ll> vl;
typedef pair<ll, ll> pll;

#define St first
#define Nd second
#define Pb push_back
#define print_pair(p) "{" << (p).St << ", " << (p).Nd << "} "
#define list_format(i, n) (i!=n? " ":"\n")
#define endl "\n"
#define sz(a) (int)a.size()

#define REP(i,a,b) for(int i = a; i <= b; i++)
#define REV(i,a,b) for(int i = a; i >= b; i--)

#define AritSum(a,d,n) ((n)*(2*(a)+((n)-1)*(d)))/2
#define Log(base, num) log2(num)/log2(base)

#define MOD 1000000007
#define INF 1e18

// ******************** Add-on *****************************

// ******************** Add-on *****************************

// ************* MAIN *******************

int A[100000];
int n, x;

void solve() {
    cin >> n >> x;
    REP(i,0,n-1) cin >> A[i];
    int it = 0;
    bool working = true;
    ll sum = accumulate(A, A + n, 0ll);
    while (working) {
        REP(i,0,n-1) {
            if (!working) break;
            if (A[i]%x == 0) sum += (ll)A[i] * (ll)pow(x, it), A[i] /= x;
            else working = false;
        }
        it++;
    }
    cout << sum << endl;
}

/*
g++ -std=c++14 -Wall -Wextra -O2 Test.cpp -o Test
./Test < in.txt

*/
int main() {    
    int _=1;
    cin>>_;
    REP(t,1,_) {
        // cout << "Case #" << t << ": ";
        solve();
        // cout << ((solve())? "YES" : "NO") << endl;
    }
    return 0;
}
```