Zulu is a very lazy kid. He always try to optimize everything in order to do minimal work possible. Once while setting alarm, he was stuck and needed your help?
You are given N clocks. Initially all these clocks have some fixed time in the format \(HH:MM:SS\) which follow standard \(24\) hour clock rule i.e. hour's clock is between \(00\) to \(23\)(both inclusive), minute's and second's clock are between \(00\) to \(59\)(both inclusive). Now, You need to set K alarm times which will be provided again in the same format \(HH:MM:SS\) out of these N clocks. Now the only operation you are allowed is to shift the hour, minute or the second clock times by 1 unit in either of the directions. i.e. You can either increase or decrease the given time. The cost of the above operation is 1 unit.
Now, note that the usual clock rules will apply while changing the second, minute or hour clock values. i.e. when second's clock is on \(59\) seconds and you make it to \(60\), instead of getting \(60\), you get \(00\) and minute's clock gets increased by 1 unit. On the other hand if you have \(00\) second and you try to decrease it by 1, you get \(59\) seconds and minute clock will get decreased by 1 unit. Similar changes for minute's clock will lead to change in the hour's clock. Note that there is no change in other clocks while we change the hour's clock i.e. hour clock when increased on \(23\) will go back to \(00\) or vice versa without affecting minute's and second's clock.
Calculate minimum number of operations needed to make a subset of K clocks of the N clocks equal to the set of K alarms.
Input:
First line of input contains T denoting number of test cases. For each of the test cases, first line contains two integers N denoting number of clocks and K denoting number of alarm times needed to be set. Now there follow \(N + K\) lines where first N lines contains list of available times on the clocks and next K lines contains the alarm times which you need to set using the given N clocks. Note that each of the time is given in the format \(HH:MM:SS\) only.
Output:
For each of the test cases, output in a single line the minimum number of operations required to set all alarms successfully.
Constraints:
\( 1 \le T \le 2\)
\( 1 \le N \le 50\)
\( 1 \le K \le 17 \)
\( K \le N \)