YO!

Stuck in traffic one day, you glance at the pickup truck ahead and notice the word "YO" on its tailgate. Looking closer, you realize the driver owns a Toyota and has simply painted over the "TO" and the "YA". As the cars keep crawling forward, you start to wonder how well this trick would work on other words.

You are given a starting word and a dictionary. Count how many ways you can paint over some of the letters of the starting word so that the letters that remain, read from left to right, spell one or more dictionary words.

Painted-over letters act as blank gaps: separate words need not be adjacent, and a single word may contain embedded gaps. Each distinct paint-over pattern is counted once, and a pattern that yields several words (including the same word appearing in more than one place) is counted separately from a pattern that yields a single word. Within one pattern the words may never overlap: every remaining letter belongs to exactly one word, and the words appear in left-to-right order.

For example, if the dictionary contains "he" and "vet" and the starting word is "CHEVROLET", there are four possible paint-over patterns (a dot marks a painted-over letter):

   .HE......
   .H.....E.
   ...V...ET
   .HEV...ET

By contrast, "CHEVROLET" can form each of "hoe" and "vet" on its own, but no single pattern can spell both at the same time, because the two words would have to share a letter.

The first line contains an integer $N$ ($1 \le N \le 100$), the number of data sets.

Each data set starts with a line of the form "$X$ $S$". The integer $X$ ($1 \le X \le 200000$) is the number of dictionary words for this data set, and the string $S$ is the starting word, whose length is between 1 and 30 characters. The next $X$ lines each contain one dictionary word, also between 1 and 30 characters long.

The starting word is always given in upper case, while dictionary words may be in mixed case; letters are matched regardless of case. Neither the starting word nor any dictionary word contains blanks, no dictionary word is repeated within a data set, and the dictionary words are given in no particular order.

For each data set, print a single line containing one integer: the number of distinct paint-over patterns whose remaining letters spell one or more dictionary words. At least one letter must be painted over for a pattern to count, so a dictionary word equal to the entire starting word does not count on its own. You may assume that the number of qualifying patterns in a single data set does not exceed 300000.