#include <bits/stdc++.h>
using namespace std;

int tcase,n,m;
int lst[10010];
long long ans;

int fac[2010];
long long f[2010];

int gcd(int a,int b)
{
    int c;
    if(a<b) swap(a,b);
    for(c=a%b;c;a=b,b=c,c=a%b);
    return b;
}

int main()
{
    int i,j,cnt;
    scanf("%d",&tcase);
    for(int cas=1;cas<=tcase;cas++)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&lst[i]);
            lst[i] = gcd(lst[i],m);
        }
        sort(lst+1,lst+1+n);
        n = unique(lst+1,lst+1+n)-lst-1;
        
        for(i=1,cnt=0;i*i<=m;i++) if(m%i == 0)
        {
            fac[++cnt] = i;
            if(m/i != i) fac[++cnt] = m/i;
        }
        sort(fac+1,fac+1+cnt);
        for(i=cnt;i;i--)
        {
            f[i] = 1LL*(m-fac[i])*(m/fac[i])/2;
            for(j=cnt;j>i;j--) if(fac[j]%fac[i] == 0) f[i] -= f[j];
        }
        
        ans = 0;
        for(i=1;i<=cnt;i++) for(j=1;j<=n;j++) if(fac[i]%lst[j] == 0)
        {
            ans += f[i];
            break;
        }
        printf("Case #%d: %I64d\n",cas,ans);
    }
    return 0;
}