Jumble Match

No attempts yetTime limit1sMemory limit128 MB

Problem

A pattern is a string of lowercase letters and underscores _. One underscore matches any single letter.

A word matches the pattern if some jumble (permutation) of the pattern characters equals a substring of the word. Put another way, for a pattern of length pp and a word ww, the word matches when you can pick a substring of ww of length pp and place every pattern character at a distinct position inside it, each letter onto an equal letter and each underscore onto any position left over.

The pattern cat matches cat, scat, and cater, since cat is a substring of each. The characters may be rearranged, so it also matches tacit, latch, and fact, which contain a permutation of cat. The pattern cat_ matches any word holding a 4-character substring made of c, a, t and one further letter, so it matches track, cant, and crate.

Given a list of words, count how many of them match the pattern.

Input

The input holds several tests.

Each test starts with a line holding the pattern to search for. The pattern consists of lowercase letters and underscores only, and its length pp satisfies 1p<1001 \le p < 100. A line holding a single dot . ends the whole input.

The lines after the pattern hold the words. Each of those lines starts with the number of words on that line, kk (1k101 \le k \le 10), followed by the kk words, with a single space between items. Words consist of lowercase letters only, and their length mm satisfies 1<m<201 < m < 20. A line whose word count is 00 ends that test, and the next line starts a new test.

Output

Print one line per test in the format Test x: y, where xx is the test number counting from 1 and yy is how many of that test's words match the pattern. If the same word appears more than once, count it once for every appearance.