Два професори
Є два професори у великій Академії X, які дійсно не ладнають один з одним. Щоб не розкривати їхні імена, ми назвемо їх 1 і 2. Академія наймає рівно n професорів; кожен з них має прочитати рівно одну лекцію. Оскільки їхні розклади досить щільні (вони ж професори, пам'ятаєте?), час початку та закінчення кожної лекції вже зафіксовано. Однак ще не визначено, де саме відбудеться кожна лекція. Очевидно, що неможливо запланувати дві лекції в одній аудиторії, якщо їхні тривалості перетинаються; з іншого боку, це можливо, якщо одна з них починається точно в той момент, коли інша закінчується.
Ваше завдання — знайти мінімальну кількість аудиторій, які дозволять розмістити всі лекції. Але знайте, що професори 1 і 2 настільки ненавидять один одного, що ніколи не будуть читати свої лекції в одній аудиторії.
Вхідні дані
Вхідні дані містять кілька тестових випадків. Перша строка містить кількість тестових випадків t (t ≤ 250). Кожен тест починається з рядка, що містить кількість професорів n (2 ≤ n ≤ 10^5). Наступні n рядків містять два цілі числа start[i] та end[i] (0 ≤ start[i] < end[i] ≤ 10^9), час початку та закінчення лекції, яку читає i-й професор, відповідно. Загальний розмір вхідних даних не перевищуватиме 50MB.
Вихідні дані
Для кожного тестового випадку виведіть мінімальну кількість аудиторій, необхідних для розкладу всіх лекцій.