Scrabble

The game of Scrabble is played with tiles. Each tile either has a single letter written on it, or it is blank. A blank tile may be used to represent any letter of your choice. On your turn, you arrange tiles to form a word. Each tile may be used at most once, and you do not have to use every tile. Given a set of Scrabble tiles and a dictionary, determine how many words in the dictionary can be formed using the given tiles.

The input contains multiple test cases. In each test case, the first line contains a positive integer $n \le 1000$, the number of words in the dictionary. Each of the next $n$ lines contains one string of 1 to 7 uppercase letters, a word in the dictionary. No word appears twice. The following line contains a single string describing the tiles you have: an uppercase letter is a tile bearing that letter, and an underscore (_) is a blank tile. This string is 1 to 7 characters long and may contain duplicate tiles. The input ends with a test case where $n = 0$, which must not be processed.

For each test case, print a single line containing the number of dictionary words that can be spelled with the given tiles.

In the first example, tiles _PIZA (one blank plus P, I, Z, A) spell PIZZA as PIZ_A, ZA as ZA, and PITA as PI_A, for three words. There are not enough tiles for PROGRAM or CONTEST. In the second example, tiles A__AA__ (three A tiles and four blanks) spell BANANAS as _A_A_A_ and FIGS as ____, but CARROTS would need six blanks in addition to the A, so only two words can be formed.