（本篇博客同步于CSDN）

如果 $x|q$，设 $t=\frac{q}{x}$，那么 $q$ 会分裂成 $x$ 个 $t$。而如果 $x|t$，那么这 $x$ 个 $t$ 又会分裂出 $x^{2}$ 个 $\frac{t}{x}$……很显然这是一个有终点的循环，每循环一次就会多出 $x^{k}$ 个 $\frac{q}{x^{k}}$。我们把当前循环中 $q$ 分裂出的 $x^{k}$ 个数看做 一个整体，每次循环都会使得数组里的元素和增加 $q$。同时，由于 $q\le 10^{9}$，所以循环次数为 $O(\log_{x}{q})$，这是一个上界为 $30$ 的数，直接模拟这个循环即可。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;

inline int read(){
    int x=0,fh=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') fh=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*fh;
}

const int N=1e5+5;
int a[N],cnt[N];

void work(){
    int n=read(),x=read();
    ll ans=0;
    fo(i,1,n) a[i]=read(),cnt[i]=0,ans+=a[i];
    fo(i,1,n){
        int t=a[i];
        while(t%x==0){
            t/=x;
            cnt[i]++;
        }
    }
    int flag=1;
    while(flag){
        fo(i,1,n){
            if(cnt[i]) cnt[i]--,ans+=a[i];
            else{
                flag=0;
                break;
            }
        }
    }
    printf("%lld\n",ans);
    //puts("");
}
int main(){
    int T=read();
    while(T--){
        work();
    }
    return 0;
}