Description

一条铁路线有两个车站，A 和 B。列车可以在一天内多次往返于 A 和 B 之间。当一列列车从 A 到达 B（或从 B 到达 A）后，需要一定的时间才能准备好进行返程——这段时间称为周转时间。例如，如果一列列车在 12:00 到达，且周转时间为 0 分钟，则它可以在 12:00 立即出发。

列车时刻表给出了所有 A 到 B 和 B 到 A 之间的行程的出发和到达时间。铁路公司需要知道，为了使时刻表能够顺利运行，早上分别需要在 A 和 B 各准备多少列列车：每当有列车需要从 A 或 B 出发时，必须有一列已经准备好的列车在该站等候。铁路线中有会车段，因此列车的到达顺序不一定与出发顺序相同。列车不能执行时刻表上未列出的行程。

Input Format

输入的第一行为测试用例数 $N$。接下来有 $N$ 组测试数据。

每组测试数据包含若干行。第一行为周转时间 $T$，单位为分钟。下一行为两个整数 $N_A$ 和 $N_B$，分别表示从 A 到 B 和从 B 到 A 的行程数。接下来有 $N_A$ 行，每行包含两个字段，分别为该行程的出发时间和到达时间，格式为 HH:MM。每个行程的出发时间早于到达时间，所有出发和到达均在同一天内。行程的顺序不一定按时间排序。小时和分钟均为两位数，前导零补齐，采用 24 小时制（00:00 到 23:59）。

在这 $N_A$ 行之后，有 $N_B$ 行，给出从 B 到 A 的行程的出发和到达时间。

Output Format

对于每组测试数据，输出一行，格式为 "Case #$x$: "，后接需要在 A 和 B 各自准备的列车数量。

2
5
3 2
09:00 12:00
10:00 13:00
11:00 12:30
12:02 15:00
09:00 10:30
2
2 0
09:00 09:01
12:00 12:02

Case #1: 2 2
Case #2: 2 0

Hint

数据范围

小数据集（5 分，测试点 1 - 可见）

• $1 \leq N \leq 20$
• $0 \leq N_A, N_B \leq 20$
• $0 \leq T \leq 5$

大数据集（20 分，测试点 2 - 隐藏）

• $1 \leq N \leq 100$
• $0 \leq N_A, N_B \leq 100$
• $0 \leq T \leq 60$

由 ChatGPT 4.1 翻译