#1243 Sentence Decomposition
Little Bonnie and her friends were dismayed to learn that their parents were reading all of their private communications. They decided to invent a new language that would allow them to talk freely. What they finally came up with was a language where sentences are built using a special method.
All the valid words that can be used in the new language are given in the dictionary. A sentence is a concatenation (with no spaces) of a sequence of valid words. Each valid word can appear 0 or more times in the sentence. What makes the language special is that each word can be transformed by rearranging its letters before being used. The cost to transform a word is defined as the number of character positions where the original word and the transformed word differ. For example, "abc" can be transformed to "abc" with a cost of 0, to "acb", "cba" or "bac" with a cost of 2, and to "bca" or "cab" with a cost of 3.
Although several different sequences of valid words can produce the same sentence in this language, only the sequence with the least total transformation cost carries the meaning of the sentence. The advantage of the new language is that the parents can no longer understand what the kids are saying. The disadvantage is that the kids themselves also do not understand. They need your help.
Given a String X, compute the total cost of transformation of the sequence of valid words which carries the meaning of the sentence, or -1 if no such sequence exists.
The first line contains the number of test cases T (T ≤ 250).
For each test case, N, the number of words in the dictionary (1 ≤ N ≤ 50) and string X are given on the first line.
Each element of the dictionary will be given on the following N lines, one per line.
Every string will contain between 1 and 50 lowercase letters ('a' - 'z'), inclusive.
Output the answer of each test case on a separate line.
- The dictionary may contain more than one occurrences of same word.
- If a word is used multiple times in a sentence, each occurrence can be transformed differently.