#include <cmath> #include <cstdio> #include <cstring> #include <vector> #include <iostream> #include <algorithm> using namespace std; int len, dp[2000][30],pr[2000][30], cost[30][30]; char a[2000]; int solve(int pos, int last){ if(pos == len) return 0; int &ret = dp[pos][last]; if(ret!=-1) return ret; int i, r; ret = 1<<29; for(i = last;i<26;i++){ r = solve(pos+1,i) + cost[a[pos]-'a'][i]; if(r<ret){ ret = r; pr[pos][last] = i; } } return ret; } void print(int pos, int last){ if(pos == len) { printf("\n"); return; } printf("%c",pr[pos][last]+'a'); print(pos+1,pr[pos][last]); } int main() { int t,i,j; scanf("%d",&t); while(t--){ scanf("%s",a); for(i = 0;i<26;i++){ for(j = 0;j<26;j++) scanf("%d",&cost[i][j]); } len = strlen(a); memset(dp,-1,sizeof(dp)); printf("%d ",solve(0,0)); print(0,0); } return 0; }