/* */ //#pragma comment(linker, "/STACK:16777216") #include <fstream> #include <iostream> #include <string> #include <complex> #include <math.h> #include <set> #include <vector> #include <map> #include <queue> #include <stdio.h> #include <stack> #include <algorithm> #include <list> #include <ctime> #include <memory.h> #include <ctime> #define y0 sdkfaslhagaklsldk #define y1 aasdfasdfasdf #define yn askfhwqriuperikldjk #define j1 assdgsdgasghsf #define tm sdfjahlfasfh #define lr asgasgash #define eps 1e-9 //#define M_PI 3.141592653589793 #define bs 1000000007 #define bsize 256 using namespace std; long tests; string st; long cost[100][100]; long n; long dp[2000][30], par[2000][30]; long bst; long bp; int main(){ //freopen("k.in","r",stdin); //freopen("k.out","w",stdout); //freopen("C:/input.txt","r",stdin); //freopen("C:/output.txt","w",stdout); ios_base::sync_with_stdio(0); //cin.tie(0); cin>>tests; for (;tests;--tests) { cin>>st; for (int i=0;i<26;i++) for (int j=0;j<26;j++) cin>>cost[i][j]; n=st.size(); for (int i=0;i<=n;i++) for (int j=0;j<26;j++) dp[i][j]=1e9; dp[0][0]=0; for (int i=0;i<n;i++) for (int p1=0;p1<26;p1++) for (int p2=p1;p2<26;p2++) { long ts=cost[st[i]-'a'][p2]; if (dp[i+1][p2]>dp[i][p1]+ts) { dp[i+1][p2]=dp[i][p1]+ts; par[i+1][p2]=p1; } } bst=1e9; for (int i=0;i<26;i++) if (dp[n][i]<bst) bst=dp[n][i], bp=i; cout<<bst<<" "; string res=""; for (int i=n;i;--i) { res+=char(bp+'a'); bp=par[i][bp]; } reverse(res.begin(),res.end()); cout<<res<<endl; } cin.get();cin.get(); return 0;}