İki professor
Akademiya X-də bir-biri ilə heç yola getməyən iki professor var. Onların adlarını açıqlamamaq üçün biz onları 1 və 2 adlandıracağıq. Akademiyada dəqiq olaraq n professor çalışır; hər biri dəqiq olaraq bir mühazirə verməlidir. Onların cədvəlləri olduqca sıxdır (professor olduqlarını unutmayın), hər mühazirənin başlama və bitmə vaxtı artıq müəyyən edilib. Lakin, hələlik hər mühazirənin harada keçiriləcəyi müəyyən edilməyib. Aydındır ki, iki mühazirənin müddətləri üst-üstə düşərsə, onları eyni otaqda planlaşdırmaq mümkün deyil; digər tərəfdən, biri bitən kimi digəri başlasa, bu mümkündür.
Sizin vəzifəniz bütün mühazirələrin yerləşdirilməsinə imkan verən minimal otaq sayını tapmaqdır. Amma bilin ki, professorlar 1 və 2 bir-birindən o qədər nifrət edirlər ki, onlar heç vaxt eyni otaqda mühazirə verməyəcəklər.
Giriş
Giriş bir neçə test halını ehtiva edir. İlk sətir test hallarının sayını t (t ≤ 250) ehtiva edir. Hər bir test n professorun sayını ehtiva edən bir sətirlə başlayır (2 ≤ n ≤ 10^5). Sonrakı n sətir gəlir, i-ci sətir i-ci professorun verdiyi mühazirənin başlama və bitmə vaxtlarını ehtiva edən iki tam ədəd start[i] və end[i] (0 ≤ start[i] < end[i] ≤ 10^9) ehtiva edir. Girişin ümumi ölçüsü 50MB-dan çox olmayacaq.
Çıxış
Hər bir test halı üçün bütün mühazirələrin planlaşdırılması üçün lazım olan minimal otaq sayını çıxış edin.