#include <iostream> #include <string> #include <memory.h> using namespace std; string s; int c[26][26]; int cs[2000][26]; void solve() { cin >> s; int n = s.length(); for (int i = 0; i < 26; ++i) for (int j = 0; j < 26; ++j) cin >> c[i][j]; memset(cs, 1, sizeof cs); cs[0][0] = 0; for (int i = 0; i < s.length(); ++i) { int X = s[i] - 'a'; int p = cs[i][0]; for (int j = 0; j < 26; ++j) { p = min(p, cs[i][j]); cs[i + 1][j] = p + c[X][j]; } } int b = 0; for (int i = 0; i < 26; ++i) if (cs[s.length()][i] < cs[s.length()][b]) b = i; cout << cs[n][b] << ' '; string ans; ans += char('a' + b); while (n > 0) { int X = s[n - 1] - 'a'; int p = cs[n - 1][0]; for (int j = 0; j < 26; ++j) { p = min(p, cs[n - 1][j]); if (p + c[X][b] == cs[n][b]) { char cc = ('a' + j); ans = cc + ans; b = j; --n; break; } } } cout << ans.substr(1) << endl; } int main() { int t; cin >> t; while (t --> 0) solve(); return 0; }