After his first ride on vintage train, Sheldon got so excited that he downloaded the schedule of trains from LA to Napa Valley and back. He soon figured out that a train can make multiple trips from LA to Napa Valley and then back to LA. When a train arrives at Napa Valley from LA (or arrives at LA from Napa Valley), it needs a C minutes before it is ready to take the return journey. Now he wants to know minimum number of vintage train starting from LA and Napa Valley.
For Example, lets say LA is point A and Napa Valley is point B.
A train starts form A at 12.02 and reaches B at 12.03.
If it takes 1 minute to start the return trip, then the train will be ready to start from B to A at 12.04.
If there is a train scheduled to start from B at or after 12.04 then this train can make the return trip and so a new train won't be required.
First line contains no of test cases, T.
First line of each test case contains an integer C. Second line contains two integers, A and B, number of trains starting from LA and Napa Valley respectively. A + B lines follow.
Each lines contains two fields in format HH:MM (00:00 through 23:59), departure and arrival time for that trip. The departure time for each trip will be earlier than the arrival time. All arrivals and departures occur on the same day.
First A lines contains schedule of trains originating at LA. Next B lines contains schedule of trains originating at Napa Valley.
NOTE : Schedule is unsorted.
For each test case, output one line containing minimum number of trains starting at LA and Napa Valley respectively.
T <= 10
0 <= C <= 60
0 <= A, B <= 10^5
Problem Setter : Pushkar Anand
Source : Google Code Jam, Qualification Round 2008