#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 100005
#define MOD 1000000007
#define dd double
#define vi vector<int>
#define vll vector<ll>
#define forr(i,n) for(ll i=0;i<n;i++)
#define revf(i,n) for(ll i=n-1;i>=0;i--)
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep1(i,b) for(ll i=1;i<=b;i++)
#define inp(a,n) for(ll i=0;i<n;i++)cin>>a[i]
#define outp(a,n) for(ll i=0;i<n;i++)cout<<a[i]<<" "
#define outp1(a,n) for(ll i=1;i<n;i++)cout<<a[i]<<" "
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) (((a)*(b))/gcd((a),(b)))
#define pb push_back
#define mp make_pair
#define mem(x,n) memset(x,n,sizeof(x))
#define BINSC binary_search
#define BITOUT __builtin_popcount
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define test ll t; cin>>t; while(t--)
#define cn cout<<"\n";
int main()
{
     fast
     test
     {
          ll n,x;
          cin>>n>>x;
          ll ar[n];
          inp(ar,n);
          ll s1=0,s=0;
          ll ind=-1;
          forr(i,n)
          {
               s1+=ar[i];
          }
          ll v[32][n];
          forr(i,32)
          {
               forr(j,n)
               {
                    if(i==0)
                    v[0][j]=ar[j];
                    else
                    v[i][j]=1;
               }
               
          }
          forr(i,n)
          {
               ll w=1;
               if(ar[i]%x==0)
               {
                    while(ar[i]%x==0)
                    {
                         v[w][i]=ar[i]/x;
                         ar[i]=ar[i]/x;
                         w++;
                    }
               }
               else
               break;
          }
          ll q=0;
          ll c=1;
          REP(i,1,32)
          {
               forr(j,n)
               {
                    if(v[i-1][j]%x==0)
                    {
                         s+=pow(x,c)*v[i][j];
                    }
                    else
                    {
                         q=1;
                         break;
                    }
               }
               c++;
               if(q)
               break;
          }
          cout<<s+s1;cn
     }
}
### Prompt

Generate 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 ll long long int
#define N 100005
#define MOD 1000000007
#define dd double
#define vi vector<int>
#define vll vector<ll>
#define forr(i,n) for(ll i=0;i<n;i++)
#define revf(i,n) for(ll i=n-1;i>=0;i--)
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep1(i,b) for(ll i=1;i<=b;i++)
#define inp(a,n) for(ll i=0;i<n;i++)cin>>a[i]
#define outp(a,n) for(ll i=0;i<n;i++)cout<<a[i]<<" "
#define outp1(a,n) for(ll i=1;i<n;i++)cout<<a[i]<<" "
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) (((a)*(b))/gcd((a),(b)))
#define pb push_back
#define mp make_pair
#define mem(x,n) memset(x,n,sizeof(x))
#define BINSC binary_search
#define BITOUT __builtin_popcount
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define test ll t; cin>>t; while(t--)
#define cn cout<<"\n";
int main()
{
     fast
     test
     {
          ll n,x;
          cin>>n>>x;
          ll ar[n];
          inp(ar,n);
          ll s1=0,s=0;
          ll ind=-1;
          forr(i,n)
          {
               s1+=ar[i];
          }
          ll v[32][n];
          forr(i,32)
          {
               forr(j,n)
               {
                    if(i==0)
                    v[0][j]=ar[j];
                    else
                    v[i][j]=1;
               }
               
          }
          forr(i,n)
          {
               ll w=1;
               if(ar[i]%x==0)
               {
                    while(ar[i]%x==0)
                    {
                         v[w][i]=ar[i]/x;
                         ar[i]=ar[i]/x;
                         w++;
                    }
               }
               else
               break;
          }
          ll q=0;
          ll c=1;
          REP(i,1,32)
          {
               forr(j,n)
               {
                    if(v[i-1][j]%x==0)
                    {
                         s+=pow(x,c)*v[i][j];
                    }
                    else
                    {
                         q=1;
                         break;
                    }
               }
               c++;
               if(q)
               break;
          }
          cout<<s+s1;cn
     }
}
```