#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>

using namespace std;

typedef long long LL;

int T,n,m,p[20010],mark[20010],x,tot;

LL dp[20010];

int main(){

    scanf("%d",&T);

    for(int Cas=1;Cas<=T;Cas++){

        memset(dp,0,sizeof(dp));

        memset(mark,0,sizeof(mark));

        scanf("%d%d",&n,&m); tot=0;

        for(int i=1;i*i<=m;i++){

            if(m%i==0){

                p[++tot]=i;

                if(i*i!=m)p[++tot]=m/i;

            }

        }sort(p+1,p+tot+1);

        for(int i=1;i<=n;i++){

            scanf("%d",&x);

            int GCD=__gcd(x,m);

            for(int j=1;j<=tot;j++)if(p[j]%GCD==0)mark[j]=1;

        }LL ans=0;

        for(int i=tot;i;i--)if(mark[i]){

            int t=(m-1)/p[i];

            dp[i]=1LL*t*(t+1)/2*p[i];

            for(int j=i+1;j<=tot;j++)if(mark[j]&&p[j]%p[i]==0)dp[i]-=dp[j];

            ans=ans+dp[i];

        }printf("Case #%d: %lld\n",Cas,ans);

    }return 0;

}