#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <climits> #include <algorithm> using namespace std; const int MAXN = 2222; int dp[MAXN][26]; int cost[26][26]; char s[MAXN]; int main() { int cases; scanf("%d", &cases); while (cases--) { getchar(); gets(s); int n = strlen(s); for (int i = 0; i < 26; ++i) { for (int j = 0; j < 26; ++j) { scanf("%d", &cost[i][j]); } } reverse(s, s + n); for (int j = 0; j < 26; ++j) { dp[0][j] = cost[s[0] - 'a'][j]; } for (int i = 1; i < n; ++i) { for (int j = 0; j < 26; ++j) { dp[i][j] = INT_MAX; for (int k = j; k < 26; ++k) { dp[i][j] = min(dp[i][j], dp[i - 1][k] + cost[s[i] - 'a'][j]); } } } int minv = INT_MAX, p = -1; for (int j = 0; j < 26; ++j) { if (dp[n - 1][j] < minv) { minv = dp[n - 1][j]; p = j; } } cout << minv << ' '; int len = n - 1; while (len >= 0) { putchar(p + 'a'); if (len == 0) break; int q = -1; for (int j = p; j < 26; ++j) { if (dp[len - 1][j] + cost[s[len] - 'a'][p] == dp[len][p]) { q = j; break; } } // cout << q << endl; p = q; --len; } puts(""); } }