Парковка самолётов
Во время экономического кризиса Джек начал новый бизнес, связанный с воздушными перевозками, — парковку для самолетов. Он приобрел большой участок земли для парковки, но он очень узкий, поэтому самолеты могут заезжать и выезжать только в порядке Последний пришел — первый вышел (см. рисунок ниже). Джек не может перемещать самолеты с конца очереди, чтобы освободить место для других.
Из-за ограничений парковки не все запросы на парковку могут быть удовлетворены. Каждый запрос содержит запланированное время прибытия и вылета самолета. Пример ниже показывает таблицу запросов для 4 самолетов.
В этом случае можно разместить самолеты 1, 2 и 4, но невозможно разместить одновременно самолеты 2 и 3.
Иногда разные самолеты могут прибывать или покидать парковку в одно и то же время. У Джека работают лучшие экипажи, которые могут организовать парковку так, чтобы, если возможно припарковать и вытащить самолеты, они это сделают. Рассмотрим другой пример.
Хотя самолеты 5 и 6 прибывают одновременно, экипажи знают, что самолет 5 должен вылететь раньше самолета 6, поэтому сначала ставят самолет 6, а затем самолет 5.
Имея список запросов на парковку, необходимо определить максимальное количество самолетов, которые могут быть припаркованы, учитывая, что они могут вылететь только в порядке Последний пришел — первый вышел.
Входные данные
Первая строка содержит целое число T, количество тестовых случаев (1 ≤ T ≤ 5). Каждый тестовый случай имеет следующий формат.
Первая строка начинается с целого числа N (1 ≤ N ≤ 300), обозначающего количество самолетов. Следующие N строк описывают таблицу запросов. Каждая строка 1+i, для 1 ≤ i ≤ N, содержит два целых числа S_i и T_i, (0 ≤ S_i < T_i ≤ 1000000000), которые являются запланированным временем прибытия и вылета для самолета i.
Выходные данные
Для каждого тестового случая ваша программа должна вывести одно целое число — максимальное количество самолетов, которые могут быть припаркованы на парковке Джека.