#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include <iomanip>
#include<climits>

using namespace std;

//=========================MACROS====================================
#define GSK ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define ll long long
#define fo(i,n) for(int i=0;i<(n);i++)
#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 tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define mod 1e9+7
#define INF 0x3f3f3f3f
#define print2(a,b) cout<<#a<<"="<<(a)<<" "<<#b<<"="<<(b)<<endl;
#define print3(a,b,c) cout<<#a<<"="<<(a)<<" "<<#b<<"="<<(b)<<" "<<#c<<"="<<(c)<<endl;


//========================TypeDefs===================================
typedef vector<int>	vi;
typedef pair<int,int> ii;

//========================FUNCTIONS==================================
inline ll ModPower(ll x, ll y, ll p = mod)
{
    ll res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
inline ll ModAdd(ll a, ll b, ll m = mod)
{
    a += b;
    if (a >= m)
        a -= m;
    return a;
}
 
inline ll ModMul(ll a, ll b, ll m = mod)
{
    return ((a % m) * (b % m)) % m;
}
// Returns n^(-1) mod p
int ModInverse(int n, int p)
{
	return ModPower(n, p - 2, p);
}
int nCr(int n, int r, int p=mod)
{
	// Base case
	if (r == 0)
		return 1;
 
	// Fill factorial array so that we
	// can find all factorial of r, n
	// and n-r
	int fac[n + 1];
	fac[0] = 1;
	for (int i = 1; i <= n; i++)
		fac[i] = (fac[i - 1] * i) % p;
 
	return (fac[n] * ModInverse(fac[r], p) % p * ModInverse(fac[n - r], p) % p) % p;
}

int BinaryToInt(string& s){
    int m=0;
	int n=s.length();
	for(int i=n-1;i>=0;i--){
	    m=m<<1;// not just m<<1;
	    if(s[i]=='1'){
	        m+=1;
	    }
	}
	return m;
}
string IntToBinary(int x){
	string s="";
	for(int i=12;i>=0;i--){
		if(x & (1LL<<i)) // ( 1 & (x>>i))
		s+='1';
		else
		s+='0';
	}
	return s;
}
/*
FUNCTIONS :

ModPower();
ModAdd();
ModMul();
ModInverse();// Returns n^(-1) mod p
nCr();
BinaryToInt();
IntToBinary
*/
//===========================CODE===================================


void solve(){
	int n,x;
	cin>>n>>x;
	vector<pair<int,int>> v;
	fo(i,n){
		int x;
		cin>>x;
		v.push_back(mp(x,1));
	}
	bool ok=1;int i=0;
	while(ok){
		if(v[i].F%x==0){
			int temp=v[i].F/x;
			
				v.push_back(mp(temp,x*v[i].S));
			
		}
		else{
			ok=0;
		}
		i++;
	}
	int sum=0;
	for(auto x: v){
		sum+=x.F*x.S;
	}

	cout<<sum<<endl;
	// cout<<(pos?"YES\n":"NO\n");
}
/*

*/

int32_t main()
{
	GSK;
	//ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int cases=1;
	//cout<<"How many test cases?\n";
	cin >> cases;
	for(int t_case=1;t_case<=cases;t_case++)
	{
		//cout<<"Enter values for testcase "<<t_case<<endl;
		solve();
	}
	return 0;
}

//END - Effort Never Dies :)

### Prompt

Please create a solution in Cpp 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<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include <iomanip>
#include<climits>

using namespace std;

//=========================MACROS====================================
#define GSK ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define ll long long
#define fo(i,n) for(int i=0;i<(n);i++)
#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 tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define mod 1e9+7
#define INF 0x3f3f3f3f
#define print2(a,b) cout<<#a<<"="<<(a)<<" "<<#b<<"="<<(b)<<endl;
#define print3(a,b,c) cout<<#a<<"="<<(a)<<" "<<#b<<"="<<(b)<<" "<<#c<<"="<<(c)<<endl;


//========================TypeDefs===================================
typedef vector<int>	vi;
typedef pair<int,int> ii;

//========================FUNCTIONS==================================
inline ll ModPower(ll x, ll y, ll p = mod)
{
    ll res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
inline ll ModAdd(ll a, ll b, ll m = mod)
{
    a += b;
    if (a >= m)
        a -= m;
    return a;
}
 
inline ll ModMul(ll a, ll b, ll m = mod)
{
    return ((a % m) * (b % m)) % m;
}
// Returns n^(-1) mod p
int ModInverse(int n, int p)
{
	return ModPower(n, p - 2, p);
}
int nCr(int n, int r, int p=mod)
{
	// Base case
	if (r == 0)
		return 1;
 
	// Fill factorial array so that we
	// can find all factorial of r, n
	// and n-r
	int fac[n + 1];
	fac[0] = 1;
	for (int i = 1; i <= n; i++)
		fac[i] = (fac[i - 1] * i) % p;
 
	return (fac[n] * ModInverse(fac[r], p) % p * ModInverse(fac[n - r], p) % p) % p;
}

int BinaryToInt(string& s){
    int m=0;
	int n=s.length();
	for(int i=n-1;i>=0;i--){
	    m=m<<1;// not just m<<1;
	    if(s[i]=='1'){
	        m+=1;
	    }
	}
	return m;
}
string IntToBinary(int x){
	string s="";
	for(int i=12;i>=0;i--){
		if(x & (1LL<<i)) // ( 1 & (x>>i))
		s+='1';
		else
		s+='0';
	}
	return s;
}
/*
FUNCTIONS :

ModPower();
ModAdd();
ModMul();
ModInverse();// Returns n^(-1) mod p
nCr();
BinaryToInt();
IntToBinary
*/
//===========================CODE===================================


void solve(){
	int n,x;
	cin>>n>>x;
	vector<pair<int,int>> v;
	fo(i,n){
		int x;
		cin>>x;
		v.push_back(mp(x,1));
	}
	bool ok=1;int i=0;
	while(ok){
		if(v[i].F%x==0){
			int temp=v[i].F/x;
			
				v.push_back(mp(temp,x*v[i].S));
			
		}
		else{
			ok=0;
		}
		i++;
	}
	int sum=0;
	for(auto x: v){
		sum+=x.F*x.S;
	}

	cout<<sum<<endl;
	// cout<<(pos?"YES\n":"NO\n");
}
/*

*/

int32_t main()
{
	GSK;
	//ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int cases=1;
	//cout<<"How many test cases?\n";
	cin >> cases;
	for(int t_case=1;t_case<=cases;t_case++)
	{
		//cout<<"Enter values for testcase "<<t_case<<endl;
		solve();
	}
	return 0;
}

//END - Effort Never Dies :)

```