Recycling Proteins

Proteins are large organic molecules made of amino acids arranged in a linear chain and joined by peptide bonds. The amino acids in the chain and the order in which they appear determine the physical and chemical properties of the protein. There are 20 standard amino acids, each identified by a unique 3-letter code (for example, Ala for Alanine).

Two scientists have built a machine that rearranges chains of amino acids, effectively converting one protein into another. This lets them turn organic waste into useful substances such as insulin.

The chemical processes that break and create peptide bonds are expensive, and every amino-acid chain must be processed separately. Your task is to compute the cost of transforming one chain of amino acids into another.

The costs are as follows.

• Removing one amino acid from the chain costs 2 euros.
• Inserting one amino acid costs 4 euros.
• Replacing one amino acid with another (removing one and adding another in its place) costs 5 euros.

The amino acids Lysine (Lys), Valine (Val), Arginine (Arg) and Histidine (His) are rare and more expensive: adding one of these, or replacing an amino acid with one of these, costs 1 euro more than the normal operation (so inserting a rare amino acid costs 5 euros and replacing with a rare amino acid costs 6 euros). You may assume unlimited supplies of every amino acid. Leaving an amino acid unchanged, where the two chains already agree at that position, costs nothing.

The first line contains an integer n (0 < n ≤ 10000), the number of test cases. Each test case is given as follows.

• A line with an integer k (1 ≤ k ≤ 1000), the number of amino acids in the chain to recycle.
• k lines, each a 3-letter string xi, the type of the i-th amino acid in the chain to recycle.
• A line with an integer m (1 ≤ m ≤ 1000), the number of amino acids in the chain to create.
• m lines, each a 3-letter string yj, the type of the j-th amino acid in the chain to create.

Within a single test case, at most 20 different amino acid types appear.

For each test case, print a single line with one integer: the minimum cost (in euros) of converting the chain (x1, x2, …, xk) into the chain (y1, y2, …, ym).