Generator

We can generate a random string by generating a sequence of random characters and concatenating them together. Each character is chosen independently from the first n letters in the English alphabet with equal probability. Only capital letters are used in this problem. The generation is stopped as soon as one of specific patterns occurs in the random string.

Your task is to predict the expected length of the generated string.

Standard input will contain multiple test cases.

First line is the number of case x.

Each test case consists of integer N (1<=N<=8) which is the number of letters used, and M (1<=M<=10) which is the number of patterns used. The following M lines contain the patterns which are non-empty strings consisting of letters chosen from the first N upper case English letters. The length of any pattern will not exceed 10.

For each test case, print the expected length of the generated random string. All output numbers are rounded to the second digit after the decimal point.

4
2 1
A
2 1
ABA
3 1
AAAAA
2 2
A
AA

2.00
10.00
363.00
2.00

2009 Multi-University Training Contest 15 - Host by BUAA