#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ld double
#define llu long long unsigned

int prime[300000],nprime;
int mark[1000000];
void sieve(int n)
{
    int i,j,limit= sqrt(n*1.)+2;
    mark[1] = 1;
    for(i=4;i<=n;i+=2)
        mark[i]=1;
    prime[nprime++]=2;
    for(i=3;i<=n;i+=2)
        if(!mark[i])
        {
            prime[nprime++]=i;
            if(i<=limit)
            {
                for(j=i*i;j<=n;j+=i*2)
                {
                    mark[j]=1;
                }
            }
        }
}

int main()
{
    fast;
    sieve(10000);
    map < int , int > ts;
    for(int i=0;i<nprime;i++)
         ts[ prime[i] ] = 1;
    int t;
    cin>>t;
    for( int c = 1 ; c <= t ; c++ )
    {
        cout<<"Case #"<<c<<": ";
        int n , l;
        cin>>n>>l;
        vector < int > v;
        vector < int > crypto;
        for( int i = 0 ; i < l ; i++ )
        {
            int x;
            cin>>x;
            v.push_back( x );
        }
        for(int i=0;i<nprime;i++)
        {
            if( v[0] % prime[i] == 0 and ts[ v[0] / prime[i] ] == 1 )
            {
                crypto.push_back( prime[i] );
                crypto.push_back( v[0] / prime[i] );
                break;
            }
        }
        for( int i = 1 ; i < l ; i++ )
        {
            if( v[i] % crypto[ crypto.size() - 1 ] == 0 and ts[ v[i] / crypto[ crypto.size() - 1 ] ] == 1 )
                crypto.push_back( v[i] / crypto[ crypto.size() - 1 ] );
            else if( v[i] % crypto[ crypto.size() - 2 ] == 0 and ts[ v[i] / crypto[ crypto.size() - 2 ] ] == 1 )
                crypto.push_back( v[i] / crypto[ crypto.size() - 2 ] );
        }
//        for( int i = 0 ; i < crypto.size() ; i++ )
//            cout<<crypto[i]<<" ";
//        cout<<endl;
        vector < int > copyV;
        copyV = crypto;
        sort( copyV.begin() , copyV.end() );
        map < int , char > m;
        m[ copyV[0] ] = 'A';
        char ch = 'B';
        for( int i = 1 ; i < crypto.size() ; i++ )
            if( copyV[i] != copyV[i-1] )
                m[ copyV[i] ] = ch++;
//        for( int i = 0 ; i < crypto.size() ; i++ )
//            cout<<m[ copyV[i] ]<<" "<<copyV[i]<<endl;
        for( int i = 0 ; i < crypto.size() ; i++ )
            cout<<m[ crypto[i] ];
        cout<<endl;
    }
    return 0;
}