SP7387 PKA - Airplane Parking

在经济危机期间，杰克看准了一个与航空旅行相关的商机，开办了一家飞机停车场。他购置了一块足够大的土地用于停放飞机，但由于地形狭长，飞机的进出只能以“后进先出”的方式进行。他的停车场空间受限，因此无法将任意一架停在内侧的飞机移出以让其他飞机通行。因为场地限制，并不能满足所有的停车请求。每个请求包含飞机的计划到达时间和计划离开时间。 以下是一个关于 4 架飞机的请求示例： | 飞机 | 到达时间 | 离开时间 | | --- | --- | --- | | 1 | 1 | 10 | | 2 | 2 | 5 | | 3 | 3 | 7 | | 4 | 6 | 9 | 在这个例子中，可以安排飞机 1、2 和 4 停放，但无法同时容纳飞机 2 和 3。各架飞机可能在同一时间计划到达或离开停车场。杰克的工作人员非常专业，他们会竭尽所能合理安排飞机的停放和移出。 再看另一个例子： | 飞机 | 到达时间 | 离开时间 | | --- | --- | --- | | 5 | 10 | 12 | | 6 | 10 | 15 | | 7 | 13 | 17 | 虽然飞机 5 和 6 同时到达，但杰克的员工了解飞机 5 必须先离开的需求，因此在两架飞机到达时，会先安排飞机 6 停入，然后再停车机 5。 基于这样的停车请求列表，你需要计算出在这个停车场中，以后进先出的方式，最多可以停放多少架飞机。

第一行包含一个整数 $T$，表示测试用例的数量（$1 < T < 5$）。接下来是每个测试用例的描述。每个用例的第一行包含一个整数 $N$（$1 < N < 300$），表示总请求的飞机数量。随后 $N$ 行描述了各个请求。第 $1 + i$ 行给出两个整数 $S_i$ 和 $T_i$（$0 < S_i < T_i < 1,000,000,000$），分别表示飞机 $i$ 的计划到达时间和计划离开时间。

对于每个测试用例，输出一行，包含一个整数，表示杰克的停车场中最多能停放的飞机数量。 **本翻译由 AI 自动生成**