#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

int dp[2000][30];
string s;
int cost[27][27];
int ntest;

int f(int x, int y){
	int  & res = dp[x][y];
	if(res!=-1) return res;
	if(x == s.length()) return res=0;
	
	res = 10000000;
	for(int i=y; i<26; i++ ){
		int temp = cost[s[x]-'a'][i] + f(x+1,i);
		res = min(res,temp);
	}
	return res;
}

void solve(){
	cin>> s ;
	//cout << s << endl;
	for(int i=0; i<26; i++){
		for(int j=0; j<26; j++){
			cin >> cost[i][j];
		}
	}
	memset(dp,-1,sizeof dp);
	int res = f(0,0);
	string r;
	int cur = 0;
	for(int i=0; i < s.length(); i++){		
		//cout << i << " "<< r << " "<< dp[i][cur] << " " << (char) ('a'+cur) << endl; 
		for(int j=cur; j<26; j++){
			if( dp[i][cur] == dp[i+1][j] + cost[s[i]-'a'][j] ){
				cur = j;
				r += (char)('a'+j);
				cur = j;
				break;
			}
		}
	}
	cout << res << " "  << r << endl;
}

int main(){
	//freopen("test.in","r",stdin);
	cin >> ntest;
	while(ntest--){
		solve();
	}	
	return 0;
}