#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <memory.h> using namespace std; #define forn(i, n) for (int i = 0; i < (int)(n); i++) int a[30][30], b[2010], f[2010][30], p[2010][30]; char s[2010]; void solve() { scanf("%s", s); int n = strlen(s); forn(i, 26) forn(j, 26) scanf("%d", &a[i][j]); forn(i, n) b[i] = s[i] - 'a'; forn(q, 26) f[0][q] = a[b[0]][q]; for (int i = 1; i < n; i++) { forn(q, 26) { f[i][q] = 1e9; forn(e, q + 1) { if (f[i-1][e] + a[b[i]][q] < f[i][q]) { f[i][q] = f[i-1][e] + a[b[i]][q]; p[i][q] = e; } } // printf("p[%d][%d] = %d\n", i, q, p[i][q]); } } int bq = 0; forn(q, 26) if (f[n-1][q] < f[n-1][bq]) bq = q; int ans = f[n-1][bq]; string res = ""; for (int i = n-1; i >= 0; i--) { res += 'a' + bq; bq = p[i][bq]; } reverse(res.begin(), res.end()); printf("%d %s\n", ans, res.c_str()); } int main() { int tc; scanf("%d", &tc); while (tc--) { solve(); } return 0; }