Təyyarə Dayanacağı
Bu iqtisadi böhran dövründə, Cek hava nəqliyyatı ilə bağlı maraqlı bir işə başlayıb - təyyarələr üçün dayanacaq xidməti. O, təyyarələri park etmək üçün böyük bir torpaq sahəsi alıb. Lakin sahə çox dar olduğundan, təyyarələrin dayanacağa girib-çıxması yalnız Son-Girən İlk-Çıxan qaydasında olmalıdır (aşağıdakı şəkilə baxın). Onun yalnız dayanacaqda yerləri var, buna görə də bəzi təyyarələri sonundan çıxarıb digər təyyarələrin hərəkət etməsinə imkan verə bilməz.
Dayanacağın məhdudiyyətləri səbəbindən bütün park tələblərini qarşılamaq mümkün deyil. Hər bir tələb, təyyarənin dayanacağa gəldiyi vaxt olan planlaşdırılmış gəlmə və planlaşdırılmış çıxma vaxtlarından ibarətdir. Aşağıda 4 təyyarə üçün tələb cədvəli göstərilmişdir.
Bu halda, təyyarə 1, 2 və 4-ü yerləşdirmək mümkündür. Lakin həm təyyarə 2, həm də 3-ü yerləşdirmək mümkün deyil.
Fərqli təyyarələrin eyni vaxtda dayanacağa gəlməsi və ya çıxması mümkündür. Cek ən yaxşı heyətlə işləyir, belə ki, əgər təyyarələri park etmək və çıxarmaq mümkündürsə, onlar bunu edə biləcəklər. Başqa bir nümunəni nəzərdən keçirin.
Hərçənd təyyarə 5 və 6 eyni vaxtda gəlir, Cek'in heyəti təyyarə 5-in təyyarə 6-dan əvvəl çıxmalı olduğunu bilir, belə ki, hər iki təyyarə gəldikdə, əvvəlcə təyyarə 6-nı, sonra isə təyyarə 5-i yerləşdirirlər.
Park tələblərinin siyahısı verildikdə, bu dayanacaqda park edilə biləcək maksimum təyyarə sayını tapmaq istəyirsiniz, şərtlə ki, onlar yalnız Son-Girən İlk-Çıxan qaydasında çıxa bilərlər.
Giriş verilənləri
Birinci sətir, test halların sayı olan T tam ədədini (1 ≤ T ≤ 5) ehtiva edir. Hər bir test halı aşağıdakı formatdadır.
Birinci sətir, təyyarələrin sayı olan N tam ədədindən (1 ≤ N ≤ 300) başlayır. Növbəti N sətir tələb cədvəlini təsvir edir. Hər bir 1+i sətir, 1 ≤ i ≤ N üçün, təyyarə i üçün planlaşdırılmış gəlmə və planlaşdırılmış çıxma vaxtları olan iki tam ədəd S_i və T_i (0 ≤ S_i < T_i ≤ 1000000000) ehtiva edir.
Çıxış verilənləri
Hər bir test halı üçün, proqramınız Cek'in dayanacağında park edilə biləcək maksimum təyyarə sayını göstərən bir tam ədəd olan tək bir sətir çıxarmalıdır.