#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"); } }