#include<bits/stdc++.h>
#define MAX ((int)1e9 + 5)
#define N ((int)1e6 + 5)
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;

int status[1 + (N/32)] , primeCount[N];

vector < int > bitwiseSieve(int n)
{
    vector < int > prime;
    for(int i = 3 ; i * i <= n ; i += 2){
        int idx = i >> 5 , bit = i & 31;
        if((status[idx] & (1<<bit)) != 0) continue;
        for(int j = i*i ; j <= n ; j += (i<<1)){
            int idx = j >> 5 , bit = j & 31;
            status[idx] |= 1<<bit;
        }
    }

    prime.push_back(2);
    for(int i = 3 ; i <= n ; i += 2){
        int idx = i >> 5 , bit = i & 31;
        if((status[idx] & (1<<bit)) == 0) prime.push_back(i);
    }
    return prime;
}

int solve(int n , vector < int >& prime){
    int total = prime.size() , ans = n;
    for(int mask = 1 ; mask < (1<<total) ; mask++){
        int pro = 1;
        for(int i = 0 ; i < total ; i++){
            if(mask & (1<<i)){
                pro *= prime[i];
                if(pro > n) break;
            }
        }
        int numberOfMultiple = n / pro;
        if(__builtin_popcount(mask) % 2 == 1) ans -= numberOfMultiple;
        else ans += numberOfMultiple;
    }
    ans = ans - (primeCount[n] - total);
    if(n >= 1) ans--;
    return ans;
}

int main()
{
    /// problem: https://www.spoj.com/problems/KPRIMESB/
    fastio;
    int t , caseNo = 1;
    cin>>t;
    bitwiseSieve(1e6);
    primeCount[0] = primeCount[1] = 0;
    primeCount[2] = 1;
    for(int i = 3 ; i < N ; i++){
        int idx = i >> 5 , bit = i & 31;
        primeCount[i] = primeCount[i-1];
        if((i&1) && (status[idx] & (1<<bit)) == 0) primeCount[i]++;
    }
    while(t--){
        int n , k;
        cin>>n>>k;
        vector < int > prime(k);
        for(int i = 0 ; i < k ; i++) cin>>prime[i];
        sort(prime.begin() , prime.end());
        while(prime.size() > 0 && prime.back() > n) prime.pop_back();
        cout<<"Case "<<caseNo++<<": "<<solve(n , prime)<<endl;
    }
    return 0;
}