#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo0(i,n) for(int i=0;i<n;i++)
#define fo1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define lli long long int
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define mod 1000000007
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<string> vs;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
#define arrlen(ar) (sizeof(ar)/sizeof(ar[0]))

lli ceil_div(lli a,lli b) {
  return (a+b-1)/b;
}
//------------------------------------------
void initialize() {
  
}

void solve() {
  // remember to take int overflow into account. 
  int n,x;
  cin>>n>>x;
  lli sum=0;
  int a[n];
  fo0(i,n) {
    cin>>a[i];
    sum+=a[i];
  }
  int m=1;
  bool flag=true;
  while(flag) {
    fo0(i,n) {
      if((a[i]%x)!=0) {
        flag=false;
        break;
      }
      sum+=a[i]*m; // (q/x)*(x)*(m)
      a[i]=a[i]/x;
    }
    m*=x; // earlier i was doing m*=2, bcoz i was just taking x=2 in account bcoz of the example test case.
  }

  cout<<sum<<endl;
  
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());

    int t;
    cin>>t;
    while(t--) {
      solve();
    }

    return 0;
}

### Prompt

Your task is to create 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;
#define gc getchar_unlocked
#define fo0(i,n) for(int i=0;i<n;i++)
#define fo1(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define lli long long int
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define mod 1000000007
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<string> vs;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
#define arrlen(ar) (sizeof(ar)/sizeof(ar[0]))

lli ceil_div(lli a,lli b) {
  return (a+b-1)/b;
}
//------------------------------------------
void initialize() {
  
}

void solve() {
  // remember to take int overflow into account. 
  int n,x;
  cin>>n>>x;
  lli sum=0;
  int a[n];
  fo0(i,n) {
    cin>>a[i];
    sum+=a[i];
  }
  int m=1;
  bool flag=true;
  while(flag) {
    fo0(i,n) {
      if((a[i]%x)!=0) {
        flag=false;
        break;
      }
      sum+=a[i]*m; // (q/x)*(x)*(m)
      a[i]=a[i]/x;
    }
    m*=x; // earlier i was doing m*=2, bcoz i was just taking x=2 in account bcoz of the example test case.
  }

  cout<<sum<<endl;
  
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());

    int t;
    cin>>t;
    while(t--) {
      solve();
    }

    return 0;
}

```