#1160 셔틀버스

30  1 s   128 MB  

Description

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

Input

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

Output

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해서 스케줄대로 운행하기 위해 필요한 버스의 최소의 개수를 한 줄 하나씩 출력한다.

Sample Input

Sample Output

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