시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 110 20 17 20.482%

문제

효성이가 다니는 학교에서 멀리서 통학하는 학생들의 편의를 위해서 학교와 터미널 사이를 운행하는 셔틀버스를 도입하기로 하였다. 그리고 셔틀 버스의 운행의 스케줄은 전적으로 학생들의 의견을 따르기로 하였다. 셔틀 버스의 운행 스케줄이 주어질 때 운행에 필요한 버스의 최소의 수를 계산하는 프로그램을 작성하시오. 이때 셔틀 버스를 타고 내리는 시간은 고려하지 않는다.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T(1≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 첫 줄에 터미널까지 걸리는 시간 D(1 ≤ D ≤ 120)가 분으로 주어지고, 그 다음 줄에는 학교에서 터미널로 출발하는 시간의 수 A(1 ≤ A ≤ 20)가 주어지고 그 다음에는 A개의 출발 시간이 HH:MM(HH시 MM분)의 형식으로 한 줄에 하나씩 시간 순서대로 주어진다. 그 다음 줄에는 터미널에서 학교로 출발하는 시간의 수 B(1 ≤ B ≤ 20)가 주어지고 그 다음에는 B개의 출발 시간이 HH:MM의 형식으로 한 줄에 하나씩 시간 순서대로 주어진다. 시간은 06:00 ~ 21:00 사이의 값이 주어지며 HH와 MM은 항상 두 자리 숫자로 주어진다(한 자리 숫자일 경우에는 앞에 0을 붙인다.). 같은 출발 장소에서 같은 시각에 출발하는 스케줄이 있을 때에는 각각의 스케줄에 다른 버스가 운행되어야 한다

출력

각 테스트 케이스에 대해서 스케줄대로 운행하기 위해 필요한 버스의 최소의 개수를 한 줄에 하나씩 출력한다.

예제 입력

3
30
1
08:00
2
08:00
08:00
15
2
08:00
12:00
1
08:45
90
5
07:00
11:00
12:00
17:00
21:00
4
06:00
11:00
15:00
20:00

예제 출력

3
1
3

힌트