Secret Words

Gyuhyeon and Jinwoo have a list of secret words known only to them. A secret word may be used after rearranging its letters. The cost of using a rearranged word is the number of positions where the original word and the rearranged word have different letters.

For example, the secret word abc can become abc with cost 0; acb, cba, or bac with cost 2; and cab or bca with cost 3.

A secret sentence is made by concatenating secret words in order. The same secret word may be used multiple times, and each occurrence may be rearranged differently. For example, using abc twice can make abcacb: the first occurrence stays as abc, and the second occurrence is rearranged to acb with cost 2.

Given the available secret words and a target secret sentence, find the minimum total cost needed to make the target. If it is impossible, output -1.

The first line contains the number of test cases, T.

Each test case is given as follows.

• The first line contains the target secret sentence. It consists only of lowercase letters from a to z, and its length is between 1 and 50, inclusive.
• The second line contains the number of secret words, N. N is a natural number with 1 <= N <= 50.
• Each of the next N lines contains one secret word.

For each test case, output one line containing the minimum cost needed to make the target secret sentence. If it is impossible, output -1.