Hackers are eavesdropping communication beetwen Mirko and Slavko and trying to understand the intercepted messages.

Dictionary from Mirko and Slavko contains M words and every message which one of them send to another consists of a series of words from dictionary separated by spaces.

However, the messages which hackers are intercepting due to poor quality of their equipment are changed as follows:

1. In the message are inserted at most K noises - arbitrary strings of letters. Every noise is always inserted between two words or before the first or after the last word and never within a word. 
2. All spaces between the words in the message are deleted. 

For example, if Mirko sends a message 'mirko slavko', when hackers intercept it, it can be 'mirkoxyzslavko', where 'xyz' is a noise, and the words 'mirko' and 'slavko' are found in the dictionary.

Hackers know their dictionary and have just received a new altered message which they want to disassemble to the dictionary words and sounds. Of all possible ways in which they can do that, they are interested in the one which has the most words from the dictionary.

Write a program that, given the dictionary, the number K, and received a modified message obtained as described above, determines a way in which the most words from dictionary are used.

Input

The first line contains number T ( 1 ≤ T ≤ 12 ) - the number of test cases.

The second line contains two integers M (1 ≤ M ≤ 1000) and K (0 ≤ K ≤ 10) - the number of words in the dictionary and the maximum amount of noise in each received message. 

The third line is the text messages received - a series of lowercase letters of length N (1 ≤ N ≤ 10 000). Each of the following M lines contains a word in the dictionary - a series of at least one and a maximum of 20 lowercase letters.

Output

In the first line of output write maximum number of words from the dictionary in disassembled message.

Example

Input:

1

5 3 
prisluskujuabcdnassumhakeri 
mirko 
nas 
slavko 
hakeri 
prisluskuju

Output:
3

Explanation: One of the messages is 'prisluskuju #### nas ### hakeri' which has two noises, and maximum of three words.