//By SiriusRen

#include <cstdio>

#include <algorithm>

using namespace std;

const int N=;

typedef long long ll;

int cases,n,m,a[N],s[N],tp,I=;

int gcd(int a,int b){return b?gcd(b,a%b):a;}

int get_phi(int x){

    int t=x;

    for(int i=;i*i<=x;i++)if(x%i==){

        t-=t/i;

        while(x%i==)x/=i;

    }if(x>)t-=t/x;

    return t;

}

int main(){

    for(scanf("%d",&cases);I<=cases;I++){

        long long ans=;tp=;

        scanf("%d%d",&n,&m);

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

            scanf("%d",&a[i]),a[i]=gcd(a[i],m);

        sort(a+,a++n);

        n=unique(a+,a++n)-a-;

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

            if(i*i==m)s[++tp]=i;

            else{

                s[++tp]=i;

                if(i!=)s[++tp]=m/i;

            }

        }

        for(int i=;i<=tp;i++)

            for(int j=;j<=n;j++)if(s[i]%a[j]==){

                ans+=get_phi(m/s[i]);break;

            }

        printf("Case #%d: %lld\n",I,1ll*ans*m/);

    }

}