#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("");
  }
}