Word Formation Challenge

In this problem, you are given a source string (S) and a list of words. Your task is to determine how many words from this list can be formed using the characters of (S) without reusing any character. In other words, for each word (w) in the list, you must verify if, for every character (c) in (w), the number of occurrences of (c) in (w) does not exceed the number of occurrences of (c) in (S). More formally, let (freq_S(c)) be the frequency of character (c) in (S) and (freq_w(c)) be the frequency of character (c) in (w). The word (w) can be formed if and only if (freq_w(c) \leq freq_S(c)) for every character (c) in (w).

For each test case, output the count of words that satisfy the above condition.

inputFormat

The input is given via standard input (stdin).

The first line contains a single integer (T) indicating the number of test cases. Each test case is described as follows:

• The first line of a test case contains the string (S).
  
• The second line contains an integer (N) representing the number of words to check.
  
• The following (N) lines each contain a single word.
  
  It is guaranteed that all strings contain only lowercase English letters.

outputFormat

For each test case, output a single line on standard output (stdout) containing one integer — the number of words that can be formed from (S) without reusing any letter.## sample

2
aabbcc
4
abc
aaa
bbb
cca
abcdefg
3
abcd
ef g
hij

2
2