/***********Template Starts Here***********/
#include <bits/stdc++.h>

#define pb push_back
#define nl puts ("")
#define sp printf ( " " )
#define phl printf ( "hello\n" )
#define ff first
#define ss second
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define MP make_pair
#define FOR(i,x,y) for(int i = (x) ; i <= (y) ; ++i)
#define ROF(i,x,y) for(int i = (y) ; i >= (x) ; --i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define NUMDIGIT(x,y) (((int)(log10((x))/log10((y))))+1)
#define SQ(x) ((x)*(x))
#define ABS(x) ((x)<0?-(x):(x))
#define FABS(x) ((x)+eps<0?-(x):(x))
#define ALL(x) (x).begin(),(x).end()
#define LCM(x,y) (((x)/gcd((x),(y)))*(y))
#define SZ(x) ((int)(x).size())

using namespace std;

typedef long long vlong;
typedef unsigned long long uvlong;
typedef pair < int, int > pii;
typedef pair < vlong, vlong > pll;
typedef vector<pii> vii;
typedef vector<int> vi;

const vlong inf = 2147383647;
const double pi = 2 * acos ( 0.0 );
const double eps = 1e-9;

/***********Template Ends Here***********/
vector<int> prime;
char stat[1000100];

///Generate primes till n
void sieve( int n ) {
    prime.pb ( 2 );
    int sqrtn = sqrt ( n );

    for ( int i = 3; i <= sqrtn; i += 2 ) {
        if ( stat[i] == 0 ) {
            for ( int j = i * i; j <= n; j += 2 * i ) stat[j] = 1;
        }
    }
    for ( int i = 3; i <= n; i += 2 ) if ( stat[i] == 0 ) prime.pb ( i );
}

///Calculate phi(n)
vlong calcPhi ( vlong n ) {
    vlong res = n;
    int sqrtn = sqrt ( n );
    for ( int i = 0; i < prime.size() && prime[i] <= sqrtn; i++ ) {
        if ( n % prime[i] == 0 ) {
            while ( (n % prime[i]) == 0 ) {
                n /= prime[i];
            }
            res /= prime[i];
            res *= prime[i] - 1;
        }
    }
    if ( n != 1 ) {
        res /= n;
        res *= n - 1;
    }

    return res;
}

vector < vlong > ddd, phi;

int main () {
    sieve ( 1000000 );

    int kase, cnt = 0;
    scanf ( "%d", &kase );

    while ( kase-- ) {
        vlong n, q;
        scanf ( "%lld %lld", &n, &q );

        ///Find all divisors of n
        ddd.clear();
        int sqrtn = sqrt ( n ) + eps;
        FOR(i,1,sqrtn) {
            if ( ( n % i ) == 0 ) {
                ddd.pb ( i );
                if ( n / i != i ) ddd.pb ( n / i );
            }
        }

        sort ( ALL(ddd) );

        phi.clear();
        FOR(i,0,SZ(ddd)-1){
            phi.pb ( calcPhi( n / ddd[i] ) );
            if ( i ) phi[i] += phi[i-1]; ///Make it cumulative array of phi value
        }

        printf ( "Case %d\n", ++cnt );
        while ( q-- ) {
            vlong x;
            scanf ( "%lld", &x );

            if ( x >= n ) { ///All
                printf ( "%lld\n", n );
                continue;
            }
            if ( x < 1 ) { ///None
                printf ( "%lld\n", 0 );
                continue;
            }

            int pos = upper_bound ( ALL(ddd), x ) - ddd.begin();

            pos--;

            printf ( "%lld\n", phi[pos] );
        }
    }

    return 0;
}