#include<bits/stdc++.h> using namespace std; #define PB push_back #define MP make_pair #define F first #define S second #define SZ(a) (int)(a.size()) #define SET(a,b) memset(a,b,sizeof(a)) #define LET(x,a) __typeof(a) x(a) #define TR(v,it) for( LET(it,v.begin()) ; it != v.end() ; it++) #define rTR(v,it) for( LET(it,v.rbegin()) ; it != v.rend() ; it++) #define repi(i,n) for(int i=0; i<(int)n;i++) #define si(n) scanf("%d",&n) #define sll(n) scanf("%lld",&n) #define DRT() int t; cin>>t; while(t--) #define TRACE //FILE *fin = freopen("in","r",stdin); //FILE *fout = freopen("out","w",stdout); #ifdef TRACE #define trace1(x) cerr << #x << ": " << x << endl; #define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl; #define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl; #define trace4(a, b, c, d) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl; #define trace5(a, b, c, d, e) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl; #define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl; #else #define trace1(x) #define trace2(x, y) #define trace3(x, y, z) #define trace4(a, b, c, d) #define trace5(a, b, c, d, e) #define trace6(a, b, c, d, e, f) #endif typedef long long LL; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector< PII > VPII; string A; int cst[26][26]; int DP[1992][26]; int P[1992][26]; int N; int f(int x, int c) { if(x==N)return 0; if(DP[x][c]!=-1)return DP[x][c]; DP[x][c] = 101*N; for(int nc = c; nc<26; nc++) { int dd = cst[A[x]-'a'][c] + f(x+1,nc); if ( dd < DP[x][c]) { DP[x][c] =dd; P[x][c] = nc; } } return DP[x][c]; } int main() { DRT() { SET(DP,-1); cin>>A; repi(i,26) repi(j,26) si(cst[i][j]); N = SZ(A); int mn = 0; for(int i=0; i<26; i++) if(f(0,i) < f(0,mn))mn = i; cout<<f(0,mn)<<" "; repi(i,N) { printf("%c",(char)('a' + mn)); mn = P[i][mn]; } cout<<endl; } return 0; }