Паркування Літаків
Під час цієї економічної кризи Джек започаткував новий бізнес, пов'язаний з авіаперевезеннями, — парковку для літаків. Він придбав велику ділянку для паркування літаків. Однак ділянка дуже вузька, тому літаки можуть заїжджати або виїжджати з парковки лише за принципом останній зайшов — перший вийшов (див. малюнок нижче). Він має лише місця на парковці, тому не може вивести літак з кінця, щоб інші могли рухатися.
Через обмеження парковки неможливо задовольнити всі запити на паркування. Кожен запит складається з запланованого часу прибуття та відправлення, які є часом перебування літака на парковці. Нижче наведено приклад таблиці запитів для 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.
Вихідні дані
Для кожного тестового випадку ваша програма повинна вивести один рядок, що складається з одного цілого числа, максимальної кількості літаків, які можуть бути припарковані на парковці Джека.