#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e5 + 131;

LL gcd(LL a, LL b){

	return b == 0 ? a : gcd(b, a % b);

}

LL P[maxn], cnt;

void GetP(LL m){

	cnt = 0;

	for(LL i = 1; i <= sqrt(m); ++i)

	{

		if(m % i == 0)

		{

			P[cnt++] = i;

			if(i * i != m) P[cnt++] = m / i;

		}

	}

	sort(P,P+cnt);

}

LL Vis[maxn], Num[maxn];

int main()

{

	int T;

	scanf("%d", &T);

	for(int kase = 1; kase <= T; ++kase)

	{

		LL n, m;

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

		GetP(m);

		LL u;

		memset(Vis,0, sizeof(Vis));

		memset(Num,0, sizeof(Num));

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

		{

			scanf("%lld", &u);

			LL tmp = gcd(u, m);

			for(LL j = 0; j < cnt; ++j)

			{

				if(P[j] % tmp == 0)

				Vis[j] = 1;

			}

		}

		//cout << P[cnt - 1 ] << endl;

		Vis[cnt -1] = 0;

		LL Ans = 0;

		for(LL i = 0; i < cnt; ++i) // 容斥

		{

			if(Vis[i] != Num[i])

			{

				LL tmp = m / P[i], D = Vis[i] - Num[i];

				Ans += (tmp + 1) * tmp / 2 * P[i] * D;

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

				{

					if(P[j] % P[i] == 0)

					Num[j] += D;

				}

			}

		}

		printf("Case #%d: %lld\n", kase, Ans);

	}

}