Dangerous Pattern

Question

The FBI has just now got the information that the terrorists are machinating a new terroristic attack. The terrorists keep contact in some magazines, newspapers, in some crypto ways. We will say a section of text contains dangerous pattern if S[1], S[2], ..., SK appears in the specified order and does not overlap.

For example if we have
K = 2
S[1] = 'aa'
S[2] = 'ab'
the text 'aaab' contains a dangerous pattern but the text 'aab' does not. Because the appearance of 'aa' (position [1, 2]) and the appearance of 'ab' (position [2, 3]) overlaps. Neither does 'abaa' because the appearance of them ([3, 4] and [1, 2]) are not in the specified order.

Now it turns to you the task to count how many different dangerous patterns a given text contains. We will say that two dangerous patterns are different when and only when there is at least S[i] such that the appearance of S[i] in this two patterns differs.

For example, if
K = 2
S[1] = 'a'
S[2] = 'b'
text = 'aabb'
There are four different dangerous patterns in this text ([1, 3], [1, 4], [2, 3], [2, 4] represented by the position of the appearance.

The result may be too large, you need only to output the remainder that the result divides 28851.

Some constraints for this problem:

1. The total length of the S[i] does not exceed 10,000.

2. For all the string S[1], S[2], ..., S[K], there are no two string S[i] and S[j] such that S[i] is the suffix of S[j].

3. The total length of the text does not exceed 500,000.

4. The character that appears in S[i] or in the text are all latin letters in lowercases. (i.e. 'a' .. 'z')

Input

The first line of the input is a single number X (0 < X <= 10), the number of the test cases of the input. Then X blocks each represents a single test case.

For each block the first line is an integer K. Then K lines, the (i+1)-th lines represents S[i]. Then one line whose length does not exceed 500,000 represents the text.

There're NO breakline between two continuous test cases.

Output

For each block output one line that is the remainder that the number of different dangerous patterns divides 28851.

Sample Input

2
2
a
b
aabb
2
a
b
aabb

Sample Output

4
4

Answer 1

http://blog.csdn.net/whackw/article/details/46888241