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 A1 through An and Ai’s address will be calculated based on Ai-1’s address in the following manner:

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

For example, consider A1’s address to be ’abc’ and Bahman using ’bcdef’ as keyword. In this case, A2’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: 

AddressRobin’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.


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.


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

Sample Input


Sample Output


Source: 12th Iran Nationwide Internet Contest - Final