A2 - Tenisová sezóna

Časový limit: 10s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3.4, Python 3.11

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Po dlhom čase príprav a tréningov by chcel Dávid venovať svoju budúcnosť víťazstvám na tenisových turnajoch. Rýchlo si zozbieral zoznam všetkých súťaží, vypísaných na nasledujúcu sezónu. Tenis je ale populárny šport a na svete sa počas jednej sezóny odohrá mnoho turnajov. Dávid rýchlo prišiel na to, že hoci jeho tenisové schopnosti sú na úrovni svetového šampióna, nemôže sa všetkých týchto turnajov zúčastniť.

Úloha

Dávid presne vie, ktorý turnaj kedy začína aj kedy končí. Na turnaj je potrebné sa dostaviť v ďeň jeho začiatku a kedže Dávid plánuje hrať v každom turnaji finále, nie je možné odísť skôr ako turnaj skončí (teda v prípade účasti musí všetky dni vrátane začiatku aj konca venovať tomuto turnaju). Pomôže Dávidovi nájsť maximálny možný počet turnajov, na ktorých sa môže zúčastniť.

Vstup

Prvý riadok vstupu obsahuje kladné celé číslo T (1≤T≤10), určujúce počet testovacích sád. Prvý riadok testovacej sady obsahuje kladné celé číslo N, určujúce počet turnajov v nasledujúcej sezóne. Za ním nasleduje N riadkov, každý z nich popisuje jeden turnaj, tj. obsahuje dve kladné celé čísla z_i k_i určujúci začínajúci a koncový deň turnaja.

Výstup

Pre každú sadu vstupu vypíšte jeden riadok, určujúci maximálny počet turnajov, ktorých sa môže Dávid zúčastniť.

A1

1 ≤ N ≤ 20
1 ≤ z_i ≤ k_i ≤ 1000

A2

1 ≤ N ≤ 50.000
1 ≤ z_i ≤ k_i ≤ 1.000.000.000

Príklad vstupu

Príklad výstupu

4
2

07 Domáce