#include <bits/stdc++.h> using namespace std; #define ll long long int a[26][26]; int dp[2000][26]; int dp2[2000][26]; int main() { int t; cin>>t; while(t-->0) { string s; cin>>s; int n = s.size(); for(int i=0; i<26; i++) { for(int j=0; j<26; j++) { cin>>a[i][j]; } } for(int i=1; i<=n; i++) { int cur = 1e9; int k = -1; for(int j=0; j<26; j++) { if(dp[i-1][j]<cur) { cur = dp[i-1][j]; k = j; } dp[i][j] = cur+a[s[i-1]-'a'][j]; dp2[i][j] = k; } } int ans = 1e9; int k2 = -1; for(int i=0; i<26; i++) { if(dp[n][i]<ans) { ans = dp[n][i]; k2 = i; } } cout<<ans<<" "; vector<char> ret; for(int i=n; i>=1; i--) { ret.push_back((char)('a'+k2)); k2 = dp2[i][k2]; } for(int i=n-1; i>=0; i--) { cout<<ret[i]; } cout<<endl; } return 0; }