#include <bits/stdc++.h>

using namespace std;

typedef long long     LL;
typedef pair<int,int> pii;

double PI  = acos(-1);
double EPS = 1e-7;
int INF    = 1000000000;
LL INFLL   = 1000000000000000000LL;

#define fi            first
#define se            second
#define mp            make_pair
#define pb            push_back

#define input(in)     freopen(in,"r",stdin)
#define output(out)   freopen(out,"w",stdout)

#define MIN(a, b)     (a) = min((a), (b))
#define MAX(a, b)     (a) = max((a), (b))

#define RESET(a, b)   memset(a,b,sizeof(a))
#define ALL(a)        (a).begin(), (a).end()
#define SIZE(a)       (int)a.size()
#define SORT(a)       sort(ALL(a))
#define UNIQUE(a)     (a).erase( unique( ALL(a) ), (a).end() )
#define FOR(a, b, c)  for (int (a)=(b); (a)<=(c); (a)++)
#define FORD(a, b, c) for (int (a)=(b); (a)>=(c); (a)--)
#define FORIT(a, b)   for (__typeof((b).begin()) a=(b).begin(); a!=(b).end(); a++)

int mx[8] = {-1,1,0,0,-1,-1,1,1};
int my[8] = {0,0,-1,1,-1,1,-1,1};

// ----- //
char s[100005];
int dp[2000][26];
int len;
int cost[26][26];

int go(int p,int pr) {
	int &ret = dp[p][pr];
	if (ret != -1) return ret;
	if (p == len) return ret = 0;
	ret = INF;
	FOR(a,pr,25) {
		MIN(ret,cost[s[p]-'a'][a]+go(p+1,a));
	}
	return ret;
}


void trace(int p,int pr) {
	if (p == len) return;
	int ret = go(p,pr);
	FOR(a,pr,25) {
		if (ret == cost[s[p]-'a'][a]+go(p+1,a)) {
			printf("%c",char(a+97));
			trace(p+1,a);
			return;
		}
	}
	return;
}

int main() {
	int tc;
	scanf("%d",&tc);
	while(tc--) {
		RESET(dp,-1);
		scanf("%s",s);
		len = strlen(s);
		FOR(a,0,25) {
			FOR(b,0,25){
				scanf("%d",&cost[a][b]);
			}
		}
		cout << go(0,0) << " ";
		trace(0,0);
		printf("\n");
	}
}