Minimum Machines to Fulfill Order

You are given a set of machines, where each machine is represented by a string of characters. Each character in the string denotes a specific part that the machine can produce. You are also given a production order represented as a string of characters, where each character corresponds to a required part.

Your task is to determine the minimum number of machines needed such that when you combine the parts produced by these machines, you can fulfill the production order. In other words, if for each part p, the production order requires \( r(p) \) occurrences and a selected set of machines produces \( f(p) \) occurrences, then the selection is valid if \( f(p) \ge r(p) \) for all parts p.

If it is impossible to fulfill the order with any combination of the given machines, output -1.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
M
machine_1 machine_2 ... machine_M
order
... (repeated for T test cases)

Here:

• T is the number of test cases.
• For each test case, the first integer M is the number of machines.
• The next M strings represent the parts each machine can produce.
• The next string is the production order.
</p>

outputFormat

For each test case, output a single line on standard output (stdout) containing one integer: the minimum number of machines required to fulfill the order, or -1 if it is not possible.

## sample

1
4
ABC DEF AC BD
AABBCC

3

</p>