#include <bits/stdc++.h>

using namespace std;
const int SIZE = 1000+ 10 ;
const int mx = 100000 + 10 ;
vector < int > st ;
int arr [ mx ] ;
vector < int > v [ 1000000 + 10 ] ;
vector<int> prime;
int vis [ 1000000 + 10 ];
char sieve[SIZE];
void primeSieve ( int n ) {
    sieve[0] = sieve[1] = 1;

    prime.push_back(2);
    for ( int i = 4; i <= n; i += 2 ) sieve[i] = 1;

    int sqrtn = sqrt ( n );
    for ( int i = 3; i <= sqrtn; i += 2 ) {
        if ( sieve[i] == 0 ) {
            for ( int j = i * i; j <= n; j += 2 * i ) sieve[j] = 1;
        }
    }

    for ( int i = 3; i <= n; i += 2 ) if ( sieve[i] == 0 ) prime.push_back(i);
}
void dfs ( int u ){
vis [ u ] = 1;
for ( int i = 0 ; i < v [ u ].size() ; i ++ ){
     int x = v [ u ] [ i ] ;
     if ( !vis [ x ]){
        dfs ( x );
     }
}
}
void clean(){
memset( &vis, 0 , sizeof ( vis ));
st.clear();
for ( int i = 0 ; i <=1000000 ; i ++ )v[i].clear();
}
int main()
{
  // freopen("in.txt","r",stdin);
  // freopen("ind.txt","w",stdout);
   int t , l = 1 ;
   primeSieve( 1000 );
//   for ( int i = 0 ; i < prime.size() ; i ++ ) cout << prime [ i ] <<endl;
   scanf("%d",&t);
   while ( t -- ){
        int n ;
        scanf("%d",&n) ;
        for ( int i = 1 ; i <= n ; i ++ ) scanf("%d",arr + i ) ;
        int ok = 0 ;
        for ( int i = 1 ; i <= n ;  i ++ ) {
                if ( arr[ i ]== 1 )ok++;
            int p = arr[ i ];int x = 0 ;
             x = arr [ i ] ;
            for ( int j = 0 ; j < prime.size() &&  prime [ j ] * prime [ j ] <= p ; j ++  ){

                if ( x % prime[ j ] == 0 ){
                    if ( vis [ prime [ j ] ] == 0 ) {
                            st.push_back( prime [ j ]);
                            vis [ prime [ j ] ] = 1 ;
                    }
                    v [ prime [ j ] ] .push_back ( arr[ i ] );
                    v [ arr[ i ] ].push_back ( prime [ j ] );
                    while ( x % prime [ j ] == 0 ){
                        x /= prime [ j ];
                    }
                }
            }
            if ( x != 1 ){
                 if ( vis [ x ] == 0 ) {
                        st.push_back( x );
                        vis [ x ] = 1 ;
                 }
                v [ x ].push_back ( arr[ i ] );
                v [ arr[ i ] ].push_back ( x );
            }
        }

        memset( &vis , 0 , sizeof ( vis )) ;
        int cnt = 0 ;
        for ( int i = 0 ; i < st.size() ; i ++ ){
            int p = st [ i ] ;
//            cout << p << endl;
            if ( !vis[ p ]){
                dfs( p ) ;
                cnt ++ ;
            }
        }
        cnt += ok ;
        printf("Case %d: %d\n",l++,cnt);
        clean();


   }


    return  0 ;
}