#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 #define inf 1<<30

 int n,val[],dp[<<];

 char map[][];

 int main()

 {

     int _case,t=;

     scanf("%d",&_case);

     while(_case--){

         scanf("%d",&n);

         for(int i=;i<n;i++)scanf("%d",&val[i]);

         for(int i=;i<n;i++)scanf("%s",map[i]);

         fill(dp,dp+(<<n),inf);

         for(int i=;i<n;i++)dp[<<i]=val[i];

         for(int state=;state<(<<n);state++){

             if(dp[state]==inf)continue;

             for(int i=;i<n;i++)if(state&(<<i)){

                 for(int j=;j<n;j++)if(!(state&(<<j))){

                     int cnt=map[i][j]-'';

                     if(cnt==)dp[state|(<<j)]=min(dp[state|(<<j)],dp[state]+val[j]);

                     else {

                         cnt=val[j]/cnt+(val[j]%cnt!=);

                         dp[state|(<<j)]=min(dp[state|(<<j)],dp[state]+cnt);

                     }

                 }

             }

         }

         printf("Case %d: %d\n",t++,dp[(<<n)-]);

     }

     return ;

 }