/*
hdu 5514 Frogs(容斥)

problem:
有n只青蛙和围成一个圈的m个石头. 每只青蛙可以跳a[i]步. 求所有被占领过的石头的编号和

solve:
可以发现青蛙会经过 GCD(a[i],m)的倍数的点.但是有很多重复跳过的石头. 所以会想到容斥.
如果暴力肯定要GG.   可以发现青蛙只会经过gcd(x,m)的点,也就是m的因子.
所以可以把枚举m改成枚举m的因子.  然后利用容斥减去重复的就行.  

hhh-2016-08-30 16:30:55
*/
#pragma comment(linker,"/STACK:124000000,124000000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <map>
#define lson  i<<1
#define rson  i<<1|1
#define ll long long
#define clr(a,b) memset(a,b,sizeof(a))
#define scanfi(a) scanf("%d",&a)
#define scanfs(a) scanf("%s",a)
#define scanfl(a) scanf("%I64d",&a)
#define key_val ch[ch[root][1]][0]
#define inf 1e9
using namespace std;
const ll mod = 1e9+7;
const int maxn = 20005;
int fac[maxn];
int fcnt;
int vis[maxn],hac[maxn];

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

int main()
{
    int T,n,m;
//    freopen("in.txt","r",stdin);
    scanfi(T);
    int cas = 1;
    while(T--)
    {
        scanfi(n),scanfi(m);
        fcnt = 0;
        for(int i = 1;i*i <= m;i++)
        {
            if(m % i == 0)
            {
                fac[fcnt++] = i;
                if(i *i != m)
                    fac[fcnt ++ ] = m/i;
            }
        }
        sort(fac,fac+fcnt);
//        for(int i = 0;i < fcnt;i++)
//            cout << fac[i] <<" ";
//        cout <<endl;
        int x;
        clr(vis,0),clr(hac,0);
        for(int i = 1;i <= n;i++)             //处理会经过哪些因子
        {
            scanfi(x);
            x = gcd(x,m);
            for(int j = 0;j < fcnt;j++)
            {
                if(fac[j] % x== 0)
                    vis[j] = 1;
            }
        }
        vis[fcnt-1] = 0;
        ll ans = 0;
        for(int i = 0;i < fcnt;i++)
        {
            if(vis[i] != hac[i])
            {
                int t = (m-1)/fac[i];
                ans += (ll)t*(t+1)/2 * fac[i] * (vis[i] - hac[i]);         //容斥原理. vis应该计算次数,hac已经计算次数
                t =  (vis[i] - hac[i]);
                for(int j = 0;j < fcnt;j++)
                {
                    if(fac[j] % fac[i] == 0)
                        hac[j] +=   t;
                }
            }
        }
        printf("Case #%d: %I64d\n",cas++,ans);
    }
    return 0;
}