시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 1024 MB0000.000%

문제

On teatud arv õpilasi, kellest mõned tuleks informaatikaolümpiaadi lõppvooru kutsuda. Iga õpilase kohta on teada tema tulemus eelvoorus ja tema tulemus lahtisel võistlusel. Lõppvooru kutsumiseks on ainult üks reegel: iga kutsutud õpilane peab olema igast kutsumata õpilasest vähemalt ühel võistlusel rohkem punkte saanud. Informaatikaolümpiaadi žüriid huvitab, mitu erinevat võimalust on õpilaste lõppvooru kutsumiseks. Et lõppvoor saaks toimuda, tuleb võistlusele kutsuda vähemalt üks õpilane.

입력

Selles ülesandes võib sisend koosneda mitmest alamtestist. Sisendi esimesel real on alamtestide arv $T \le 100$.

Iga alamtesti esimesel real on kõigi õpilaste arv ($1 \le N \le 200\,000$). Järgmisel $N$ real on igaühel kaks tühikuga eraldatud mittenegatiivset täisarvu, ühe õpilase punktid vastavalt eelvoorus ja lahtisel võistlusel.

Õpilaste arvude summa kõikide alamtestide peale kokku on maksimaalselt $200\,000$. Ükski õpilane ei saanud kummalgi võistlusel rohkem kui $1\,000\,000\,000$ punkti.

출력

Iga alamtesti kohta väljastada eraldi reale üks täisarv: kutsumise võimaluste arvu jääk jagamisel arvuga $1\,000\,000\,007$. Vastused tuleb anda alamtestides sisendis andmise järjekorras.

예제 입력 1

1
4
40 10
10 10
20 30
20 10

예제 출력 1

5

See sisend koosneb ainult ühest alamtestist, kus on neli õpilast. Eelvoorus sai esimene õpilane 40 punkti, teine õpilane 10 punkti, kolmas õpilane 20 punkti ja neljas õpilane 20 punkti. Lahtisel võistlusel sai esimene õpilane 10 punkti, teine õpilane 10 punkti, kolmas õpilane 30 punkti, neljas õpilane 10 punkti. Võimalikud viisid õpilaste kutsumiseks on järgmised:

  • kutsuda ainult 1. õpilane;
  • kutsuda ainult 3. õpilane;
  • kutsuda 1. ja 3. õpilane;
  • kutsuda 1., 3. ja 4. õpilane;
  • kutsuda 1., 2., 3. ja 4. õpilane.

예제 입력 2

3
4
5 0
0 0
5 0
10 0
4
100000000 100000000
100000000 1000000000
1000000000 100000000
1000000000 1000000000
6
0 1
1 0
2 1
3 0
4 1
4 0

예제 출력 2

3
5
11

See sisend koosneb kolmest alamtestist. Esimeses alamtestis on neli õpilast ning õpilasi on võimalik kutsuda kolmel erineval moel. Teises alamtestis on samuti neli õpilast ning õpilasi on võimalik kutsuda viiel erineval moel. Kolmandas ja viimases alamtestis on kuus õpilast ning õpilasi on võimalik kutsuda üheteistkümnel erineval moel.