Вибух#5546
Ви є дизайнером конвеєрної стрічки для уранових паливних стрижнів. На стрічці буде закріплено кілька L-подібних стрижнів. Кожен стрижень складається з горизонтальної та вертикальної частин, які можуть мати різну довжину.
Координати точки, де стрижень прикріплений до стрічки, мають вигляд (k; k), де — це номер стрижня. Ця точка є лівим кінцем горизонтальної частини та верхнім кінцем вертикальної частини.
Важливо пам'ятати, що надмірна концентрація урану в одному місці може призвести до небажаних наслідків (і не забувайте, хто буде відповідальний). Тому виникає питання: яка максимальна кількість стрижнів може бути розміщена так, щоб кожні два з них мали спільну точку?
Перший рядок містить кількість тестів . Далі йдуть описи самих тестів.
Кожен тест починається з числа (1 \le n \le 100\,000) в окремому рядку. Наступні рядків містять опис стрижнів. -ий рядок містить два невід'ємних цілих числа v_i, h_i \le 100\,000 — довжини вертикальної та горизонтальної частин стрижня номер .
Для кожного тесту виведіть в окремому рядку максимальну кількість стрижнів, щоб будь-які два з них мали спільну точку. Кінець стрижня вважається його частиною.
Приклад 1