Паркування Літаків#5696
Під час цієї економічної кризи Джек започаткував новий бізнес, пов'язаний з авіаперевезеннями, — парковку для літаків. Він придбав велику ділянку для паркування літаків. Однак ділянка дуже вузька, тому літаки можуть заїжджати або виїжджати з парковки лише за принципом останній зайшов — перший вийшов (див. малюнок нижче). Він має лише місця на парковці, тому не може вивести літак з кінця, щоб інші могли рухатися.
Через обмеження парковки неможливо задовольнити всі запити на паркування. Кожен запит складається з запланованого часу прибуття та відправлення, які є часом перебування літака на парковці. Нижче наведено приклад таблиці запитів для літаків.
У цьому випадку можливо розмістити літаки , та . Але неможливо одночасно розмістити літаки та .
Можливо, що різні літаки планують прибути або відправитися з парковки в один і той же час. У Джека працюють найкращі екіпажі, тому вони зможуть організувати розміщення літаків найкращим чином, щоб, якщо можливо припаркувати та вивести літаки, вони змогли це зробити. Розгляньте інший приклад.
Хоча літаки та прибувають одночасно, екіпажі Джека знають, що літак повинен виїхати раніше літака , тому, коли обидва літаки прибувають, вони спочатку ставлять літак , а потім літак .
Маючи список запитів на паркування, ви хочете знайти максимальну кількість літаків, які можуть бути припарковані на цій парковці, за умови, що вони можуть виїжджати лише у форматі останній зайшов — перший вийшов.
Перший рядок містить ціле число , кількість тестових випадків (1 \le T \le 5). Кожен тестовий випадок має наступний формат.
Перший рядок починається з цілого числа (1 \le N \le 300), що позначає кількість літаків. Наступні рядків описують таблицю запитів. Кожен рядок 1+i, для 1 \le i \le N, містить два цілі числа S_i та T_i, (0 \le S_i < T_i \le 1000000000), які є запланованим часом прибуття та запланованим часом відправлення для літака .
Для кожного тестового випадку ваша програма повинна вивести один рядок, що складається з одного цілого числа, максимальної кількості літаків, які можуть бути припарковані на парковці Джека.
Приклад 1