#include <stdio.h>
#include <string.h>
#include <set>
using namespace std;
#define ZMAX 27
#define NMAX 111111
#define LMAX 11
set<int> processed;
double T[ZMAX][ZMAX], tmp[ZMAX][ZMAX], R[ZMAX][ZMAX];
char s[LMAX], target[NMAX][LMAX];
int main() {
// freopen("y.txt", "r", stdin);
int Tests, i, j, k, p, N, K, L;
double ans, cans;
scanf("%d", &Tests);
while (Tests--) {
scanf("%d %d %s", &N, &K, s);
for (i = 1; i < ZMAX; i++)
for (j = 1; j < ZMAX; j++)
scanf("%lf", &T[i][j]);
for (i = 1; i <= N; i++)
scanf("%s", &target[i][0]);
// Raise T to the power K.
memset(R, 0, sizeof(R));
for (i = 1; i < ZMAX; i++)
R[i][i] = 1.0;
for (p = 30; p >= 0; p--) {
memset(tmp, 0, sizeof(tmp));
for (i = 1; i < ZMAX; i++)
for (j = 1; j < ZMAX; j++) {
for (k = 1; k < ZMAX; k++)
tmp[i][j] += R[i][k] * R[k][j];
}
memcpy(R, tmp, sizeof(R));
if (K & (1 << p)) {
memset(tmp, 0, sizeof(tmp));
for (i = 1; i < ZMAX; i++)
for (j = 1; j < ZMAX; j++) {
for (k = 1; k < ZMAX; k++)
tmp[i][j] += R[i][k] * T[k][j];
}
memcpy(R, tmp, sizeof(R));
}
}
L = strlen(s);
processed.clear();
for (ans = 0.0, i = 1; i <= N; i++) {
if (strlen(&target[i][0]) != L) continue;
for (cans = 1.0, k = j = 0; j < L; j++) {
cans *= R[s[j] - 'a' + 1][target[i][j] - 'a' + 1];
k = k * ZMAX + target[i][j] - 'a' + 1;
}
if (processed.find(k) == processed.end()) {
processed.insert(k);
ans += cans;
}
}
printf("%.9lf\n", ans);
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2luY2x1ZGUgPHNldD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIFpNQVggMjcKI2RlZmluZSBOTUFYIDExMTExMQojZGVmaW5lIExNQVggMTEKCnNldDxpbnQ+IHByb2Nlc3NlZDsKZG91YmxlIFRbWk1BWF1bWk1BWF0sIHRtcFtaTUFYXVtaTUFYXSwgUltaTUFYXVtaTUFYXTsKY2hhciBzW0xNQVhdLCB0YXJnZXRbTk1BWF1bTE1BWF07CgppbnQgbWFpbigpIHsKLy8JZnJlb3BlbigieS50eHQiLCAiciIsIHN0ZGluKTsKCWludCBUZXN0cywgaSwgaiwgaywgcCwgTiwgSywgTDsKCWRvdWJsZSBhbnMsIGNhbnM7CglzY2FuZigiJWQiLCAmVGVzdHMpOwoJd2hpbGUgKFRlc3RzLS0pIHsKCQlzY2FuZigiJWQgJWQgJXMiLCAmTiwgJkssIHMpOwoJCWZvciAoaSA9IDE7IGkgPCBaTUFYOyBpKyspCgkJCWZvciAoaiA9IDE7IGogPCBaTUFYOyBqKyspCgkJCQlzY2FuZigiJWxmIiwgJlRbaV1bal0pOwoJCWZvciAoaSA9IDE7IGkgPD0gTjsgaSsrKQoJCQlzY2FuZigiJXMiLCAmdGFyZ2V0W2ldWzBdKTsKCQkvLyBSYWlzZSBUIHRvIHRoZSBwb3dlciBLLgoJCW1lbXNldChSLCAwLCBzaXplb2YoUikpOwoJCWZvciAoaSA9IDE7IGkgPCBaTUFYOyBpKyspCgkJCVJbaV1baV0gPSAxLjA7CgkJZm9yIChwID0gMzA7IHAgPj0gMDsgcC0tKSB7CgkJCW1lbXNldCh0bXAsIDAsIHNpemVvZih0bXApKTsKCQkJZm9yIChpID0gMTsgaSA8IFpNQVg7IGkrKykKCQkJCWZvciAoaiA9IDE7IGogPCBaTUFYOyBqKyspIHsKCQkJCQlmb3IgKGsgPSAxOyBrIDwgWk1BWDsgaysrKQoJCQkJCQl0bXBbaV1bal0gKz0gUltpXVtrXSAqIFJba11bal07CgkJCQl9CgkJCW1lbWNweShSLCB0bXAsIHNpemVvZihSKSk7CgkJCWlmIChLICYgKDEgPDwgcCkpIHsKCQkJCW1lbXNldCh0bXAsIDAsIHNpemVvZih0bXApKTsKCQkJCWZvciAoaSA9IDE7IGkgPCBaTUFYOyBpKyspCgkJCQkJZm9yIChqID0gMTsgaiA8IFpNQVg7IGorKykgewoJCQkJCQlmb3IgKGsgPSAxOyBrIDwgWk1BWDsgaysrKQoJCQkJCQkJdG1wW2ldW2pdICs9IFJbaV1ba10gKiBUW2tdW2pdOwoJCQkJCX0KCQkJCW1lbWNweShSLCB0bXAsIHNpemVvZihSKSk7CgkJCX0KCQl9CgkJTCA9IHN0cmxlbihzKTsKCQlwcm9jZXNzZWQuY2xlYXIoKTsKCQlmb3IgKGFucyA9IDAuMCwgaSA9IDE7IGkgPD0gTjsgaSsrKSB7CgkJCWlmIChzdHJsZW4oJnRhcmdldFtpXVswXSkgIT0gTCkgY29udGludWU7CgkJCWZvciAoY2FucyA9IDEuMCwgayA9IGogPSAwOyBqIDwgTDsgaisrKSB7CgkJCQljYW5zICo9IFJbc1tqXSAtICdhJyArIDFdW3RhcmdldFtpXVtqXSAtICdhJyArIDFdOwoJCQkJayA9IGsgKiBaTUFYICsgdGFyZ2V0W2ldW2pdIC0gJ2EnICsgMTsKCQkJfQoJCQlpZiAocHJvY2Vzc2VkLmZpbmQoaykgPT0gcHJvY2Vzc2VkLmVuZCgpKSB7CgkJCQlwcm9jZXNzZWQuaW5zZXJ0KGspOwoJCQkJYW5zICs9IGNhbnM7CgkJCX0KCQl9CgkJcHJpbnRmKCIlLjlsZlxuIiwgYW5zKTsKCX0KCXJldHVybiAwOwp9Cg==