AlgoLiga 2018

Zamknięcie serwisu KickassTorrents wywołało totalny chaos wśród amerykańskiej Polonii. Nasi emigranci są zrozpaczeni ponieważ stracili główne źródło dostępu do pirackich nagrań z występami Tadeusza Drozdy. Na szczęście wzdłuż Elston Avenue w Chicago w błyskawicznym tempie uruchomionych zostało n serwerów z kopią serwisu. Każdy z nich jest wyposażony w kartę WiFi o określonym zasięgu d wyrażonym w metrach, za pomocą której komunikuje się z innymi serwerami. Znana jest również odległość x każdego z komputerów od początku Elston Avenue. Ona również wyrażona jest w metrach. Dwa serwery, oznaczmy je jako i oraz j, mogą się ze sobą komunikować poprzez sieć bezprzewodową jeżeli d_i + d_j > |x_i - x_j|. W przypadku gdy dwa komputery nie mogły komunikować się poprzez WiFi fani Taduesza połączyli je bezpośrednio światłowodem.

Niestety połączenia WiFi są bardzo zawodne, w związku z czym nasi bohaterowie zastanawiają się nad wyłączeniem części serwerów. W działaniu powinien pozostać pewien ich podzbiór, w którym każda para komputerów jest bezpośrednio połączona światłowodem. Fani Tadeusza chcą, aby znaleziony podzbiór był jak największy. Oczywiście dopuszczają oni również sytuację, gdy będzie się on składał z zaledwie jednego serwera.

Pomóż polskim emigrantom i oblicz z ilu komputerów składa się poszukiwany podzbiór oraz ile bezpośrednich połączeń światłowodowych zostało poprowadzonych pomiędzy należącymi do niego serwerami.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita t ∈ [1;5] określająca liczbę zestawów danych. W kolejnych liniach znajdują się zestawy danych.

W pierwszej linii każdego zestawu danych znajduje się jedna liczba całkowita n ∈ [1;10⁵] oznaczająca liczbę serwerów działających wzdłuż Elston Avenue. W kolejnych n liniach znajdują się po dwie liczby całkowite x ∈ [0;10⁹] i d ∈ [1;10⁹] określające odpowiednio odległość danego komputera od początku ulicy oraz zasięg jego karty WiFi wyrażone w metrach. Gwarantujemy, że odległości x nie powtarzają się w ramach zestawu danych.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać liczebność szukanego zbioru oraz liczbę bezpośrednich połączeń światłowodowych pomiędzy należącymi do niego serwerów.

Przykład

Wejście:

2
3
5 3
2 2
8 2
4
1 1
4 1
7 1
10 1

Wyjście:

2 1
4 6