/*

  HDU5514 Frogs

  http://acm.hdu.edu.cn/showproblem.php?pid=5514

  容斥原理

  *

  *

  */

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 //#define test

 using namespace std;

 const long long Nmax=1e5;

 long long n,m,a[Nmax];

 long long book[Nmax];

 long long p[Nmax];

 int cnt;

 long long num[Nmax];

 long long gcd(long long a,long long b)

 {

     if(b==0LL)

         return a;

     return gcd(b,a%b);

 }

 int main()

 {

     long long t;

     #ifdef test

     while()

     {

         long long a,b;

         scanf("%lld%lld",&a,&b);

         printf("%lld\n",gcd(a,b));

     }

     #endif

     scanf("%lld",&t);

     for(long long ttt=;ttt<=t;ttt++)

     {

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

         int flag=;

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

         {

             scanf("%lld",&a[i]);

             a[i]=gcd(a[i],m);

             if(a[i]==)

                 flag=;

         }

         if(flag)

         {

             long long ans=(m-1LL)*m/2LL;

             printf("Case #%lld: ",ttt);

             printf("%lld\n",ans);

             continue;

         }

         long long ans=0LL;

         cnt=;

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

         {

             if(m%i)

                 continue;

             p[++cnt]=i;

             if(i*i!=m)

                 p[++cnt]=m/i;

         }

         sort(p+,p++cnt);

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

             book[i]=num[i]=;

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

         {

             for(int j=;j<=cnt;j++)

                 if(p[j]%a[i]==)

                     book[j]=;

         }

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

         {

             if(book[i]!=num[i])

             {

                 long long tmp=m/p[i];

                 ans+=tmp*(tmp-1LL)/2LL*p[i]*(book[i]-num[i]);

                 tmp=book[i]-num[i];

                 for(int j=i+;j<=cnt;j++)

                     if(p[j]%p[i]==)

                         num[j]+=tmp;

             }

         }

         printf("Case #%lld: ",ttt);

         printf("%lld\n",ans);

     }

     return ;

 }