Два профессора
В Академии 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.
Выходные данные
Для каждого теста выведите минимальное количество аудиторий, необходимых для проведения всех лекций.