#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <iostream>#include <map>using namespace std;const int Z = 256;const int N = 2005;int d[Z][Z];map<char, int>mp;unsigned char str[Z], sa[N], sb[N];int na[N], nb[N];int la, lb, wa[Z], wb[Z], ca[Z], cb[Z];int idxa, idxb, dp[N][N], path[N][N];char qa[N<<1], qb[N<<1];void dfs(int i, int j) {if (!i && !j) return;if (i > 0 && j > 0 && dp[i][j] == dp[i-1][j-1] + d[sa[i]][sb[j]]) {qa[idxa++] = str[sa[i]];qb[idxb++] = str[sb[j]];dfs(i-1, j-1);} else if (i > 0 && dp[i][j] == dp[i-1][j] + wa[sa[i]]){qa[idxa++] = str[sa[i]];qb[idxb++] = str[ca[sa[i]]];dfs(i-1, j);} else {qa[idxa++] = str[cb[sb[j]]];qb[idxb++] = str[sb[j]];dfs(i, j-1);}}void gao() {memset(dp, 0x3f, sizeof (dp));dp[0][0] = 0;for (int i = 0; i <= la; ++i) {for (int j = 0; j <= lb; ++j) {if (i > 0) {dp[i][j] = min(dp[i][j], dp[i-1][j] + wa[sa[i]]);}if (j > 0) {dp[i][j] = min(dp[i][j], dp[i][j-1] + wb[sb[j]]);}if (i > 0 && j > 0) {dp[i][j] = min(dp[i][j], dp[i-1][j-1] + d[sa[i]][sb[j]]);}}}printf("%dn", dp[la][lb]);idxa = idxb = 0;dfs(la, lb);for (int i = idxa-1; i >= 0; --i) {putchar(qa[i]);}puts("");for (int i = idxb-1; i >= 0; --i) {putchar(qb[i]);}puts("");}int main() {int T;scanf("%d%", &T);while (T--) {mp.clear();memset(wa, 0x3f, sizeof (wa));memset(wb, 0x3f, sizeof (wb));scanf("%s", str+1);int len = strlen((char*)(str+1));for (int i = 1; i <= len; ++i) {mp[str[i]] = i;}scanf("%s %s", sa+1, sb+1);la = strlen((char *)(sa+1)), lb = strlen((char *)(sb+1));for (int i = 1; i <= la; ++i) {sa[i] = mp[sa[i]];}for (int i = 1; i <= lb; ++i) {sb[i] = mp[sb[i]];}for (int i = 1; i <= len; ++i) {for (int j = 1; j <= len; ++j) {scanf("%d", &d[i][j]);if (wa[i] > d[i][j]) {wa[i] = d[i][j], ca[i] = j;}if (wb[j] > d[i][j]) {wb[j] = d[i][j], cb[j] = i;}}}gao();}return 0;}
