Dr. SYG's works in the area of DNA Analysis. Once, during one of his research projects, he needed to count the number of subsequences that the first string had in common with all the others. Dr. SYG quickly wrote a computer program and was escastic to know that his results were correct. But, there was one problem, he wasn't able to ignore the repeated subsequences while counting. He tried a lot but couldn't change his program to ignore the repeated subsequences that occur in the first string. So he calls up Codecraft Team and asks them for help. And we being lazy programmers turn to you people for help.
Added Explanation : What Dr. SYG used to do was, he takes each string and stores all the subsequence of that string in a list (repitions allowed). Say he now gets three lists l1, l2 & l3 corresponding to three strings. Then he takes each distinct subsequence (say X) in l1 and found min(occur(l1, X), occur(l2, X), occur(l3, X)) and added it up for all the distincts X. Say given two string "kkk" and "k", he will form two lists "", "k", "k", "k", "kk", "kk", "kk", "kkk" and ["", "k"], respectively. Now for "" (empty string) he adds 1 (min(1, 1)) and for "k" he adds another 1 (min(3, 1)) and 0 for all other, thus obtaining his answer as 2.
First line of the input file contains number of test cases, T. This is followed by the description of T test cases. Each test case description starts with integer N, number of strings. Then next N lines contains a string each.
-> Number of test cases, T <= 100.
-> Number of strings, 2 <= N <= 3.
-> Length of each string <= 50
-> Each string will consist only of Alphabets[a-zA-Z], or digits[0-9].
For each test case you will have to output two values, x and y, separated by space. x is the answer Dr. SYG obtained and y is the answer he expects from you.
4 2 adsas ddd 2 tyy yyy 2 kkk k 2 kkk kk
2 2 4 3 2 2 4 3
Migrated from old NTUJ.
CodeCraft 2010
| No. | Testdata Range | Score |
|---|