// @author cebrusfs // headers {{{ #include<bits/stdc++.h> using namespace std; // }}} // macros {{{ #ifdef WIN32 #define LLD "%I64d" #else #define LLD "%lld" #endif #define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++) #define ALL(x) (x).begin(), (x).end() #define SZ(x) ((int)(x).size()) #define UNIQUE(x) ((x).erase(unique(ALL(x)), (x).end())) #define MS(x, v) std::fill(ALL(x), (v)); #define IOS ios_base::sync_with_stdio(false) #define REP(i,n) for(int i=0;i<(n);i++) #define REP1(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,n) for(int i=(n)-1;i>=0;i--) #define PER1(i,a,b) for(int i=(a);i>=(b);i--) #ifdef ONLINE_JUDGE #define FILEIO(x) freopen(#x ".in","r",stdin);freopen(#x ".out","w",stdout); #define FILEIOS freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); #else #define FILEIO(x) ; #define FILEIOS ; #endif typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int, int> PII; #define MP make_pair #define F first #define S second typedef vector<int> VI; #define PB push_back #define PF push_front #define PPB pop_back #define PPF pop_front // C++11 #if __cplusplus >= 201103L #define MT make_tuple typedef tuple<int, int> TII; #endif #define runtime() ((double)clock() / CLOCKS_PER_SEC) const double eps = 1e-7; // }}} #define MAX 2005 #define cMAX 26 int dp[MAX][cMAX]; int pre[MAX][cMAX]; int cost[cMAX][cMAX]; const int INF = 100 * 2000; char s[MAX]; int main() { int z; scanf("%d", &z); while (z--) { scanf(" %s", s); int n = strlen(s); for (int i = 0; i < n; ++i) s[i] -= 'a'; for (int i = 0; i < cMAX; ++i) for (int j = 0; j < cMAX; ++j) scanf("%d", &cost[i][j]); for (int j = 0; j < cMAX; ++j) dp[n][j] = INF; dp[n][cMAX - 1] = 0; pre[n][cMAX - 1] = -1; for (int i = n - 1; i >= 0; --i) { int bestk = cMAX - 1; for (int j = cMAX - 1; j >= 0; --j) { int c = cost[(int)s[i]][j]; if (dp[i + 1][bestk] >= dp[i + 1][j]) bestk = j; dp[i][j] = c + dp[i + 1][bestk]; pre[i][j] = bestk; } } int ans = INF; for (int i = 0; i < cMAX; ++i) ans = min(dp[0][i], ans); printf("%d ", ans); for (int i = 0; i < cMAX; ++i) if (dp[0][i] == ans) { int k = i; for (int j = 0; j < n; ++j) { printf("%c", 'a' + k); k = pre[j][k]; } break; } printf("\n"); } }