Amino acids are the basic elements of living cells. There are 20 different types of amino acids which are denoted by capital letters: A, C, D, E, F, G, H, I, K, L, M, N, P, Q, R, S, T, V, W, and Y. A protein is a chain of amino acids.
Viruses have been well known for their causes for many diseases. A virus is characterised by its protein. Recently, they have invented M-drug (molecular drug) - a new type of medicine to kill virus, which has shown its surprising efficiency. An M-drug is also characterised by its protein.
An M-drug characterised by a protein D, can destroy k amino acids in the protein V of a virus if there exists two number sequences (x1 < x2 <…< xk) and (y1 < y2 <…< yk) satisfying that D(xi) = V(yi) with i = 1...k. The efficiency of an M-drug on a virus is defined as the maximum number of amino acids in the protein of the virus that the M-drug can destroy.
Given the protein of a virus and the proteins of n different M-drugs, your task is to write a program to determine the maximum value of the efficiencies of those M-drugs on the virus.
The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.
For each data set, the first line contains an integer n (1 ≤ n ≤ 200) representing the number of M-drugs. The next line consists of a string with its length not exceeding 10000 representing protein of the virus. The ith line of the following n lines contains a string with a length not exceeding 500 representing the protein of the ith M-drug.
For each data set, write in one line the maximum value of the efficiencies of those M-drugs on the virus.
1 5 ENRPPNVPES TEV LNRC HKVR FWW PWP
2
Migrated from old NTUJ.
The ACM-ICPC 2010 Asia Regional Contest, Site Hanoi
| No. | Testdata Range | Score |
|---|