L :: Perfect Address

Time Limit: 2 Seconds    Memory Limit: 65536 KB

Bahman, a distinguished employee of local post office, is responsible for designating postal addresses to residences located in North Kargar Street. Each postal address is a sequence of letters placed together without any white spaces in between. Furthermore, Bahman has a specific collection of keywords which he will use as he’ll come up with new addresses.
Residences in this street are labeled A₁ through A_n and A_i’s address will be calculated based on A_i-1’s address in the following manner:

• Bahman can choose a keyword from his collection and append it to A_i-1’s address.
• Do as above but remove the duplicate letters in case the chosen keyword and A_i-1’s address overlap, i.e. keyword’s first x letters are the same as address’s last x letters.

For example, consider A₁’s address to be ’abc’ and Bahman using ’bcdef’ as keyword. In this case, A₂’s address can either be ’abcbcdef’ or ’abcdef’.
Bahman already knows that his boss, Robin, is planning to buy a house in this street and he prefers to have a postal address not bigger than L letters. In addition, Robin has certain favorite keywords and his satisfaction of the address is directly influenced by how many times these keywords will appear in the final address.
Bahman is desperate to fully satisfy Robin by arranging the address to have as many favorite keywords as possible.
For example, consider Bahman holding keywords {ab,ba}, Robin favoring keywords {aa,ab}, and L is equal to 4. The Collection of available addresses is listed below: 

Address	Robin’s Satisfaction
ab	1
ba	0
aba	1
bab	1
abab	2
abba	1
baab	2
baba	1

Your task is writing a program to find Robin’s satisfaction for the perfect address.

Input

The input contains several test cases.
In the first line of input comes T (0 < T < 64), the number of test cases.
For each test case, on the first line it will come the integer N (1 ≤ N ≤ 50) and the next N lines hold Bahman’s keywords, one in each line. After that, the integer M (1 ≤ M ≤ 50) will be given and the following M lines will have Robin’s keywords, one per line. The last line contains the integer L (1 ≤ L ≤ 50) which denotes the maximum length of the desired address.
Keywords in both lists will have a maximum length of 10 and conatin only lower-case English characters.

Output

For each test case, print a line with an integer which is the maximum satisfaction of Robin.

Sample Input

2
2
ab
ba
2
aa
ab
4
1
i
1
iii
10

Sample Output

2
8

Submit

Source: 12th Iran Nationwide Internet Contest - Final