Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule.
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/

Zadanie Miny (min)

Miny

Limit pamięci: 64 MB

Na prostej leżą miny przeciwpancerne. W razie wybuchu którejkolwiek z nich, wszystkie miny znajdujące się w jej promieniu rażenia również wybuchną. Określ, dla każdej z min, ile min wybuchnie, gdy tę jedną zdetonujemy "ręcznie".

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą dodatnią

- liczbę zestawów danych. Potem kolejno podawane są zestawy w następującej postaci:

Pierwszy wiersz opisu zestawu zawiera liczbę min (). W kolejnych wierszach znajdują się po dwie liczby całkowite , (, ) - odpowiednio położenie i promień rażenia -tej miny. Miny podane są w kolejności rosnącego położenia . Żadne dwie miny nie leżą w jednym miejscu. Zasięg miny obejmuje również miny w odległości równej jej promieniowi rażenia.

Wyjście

Dla każdego zestawu danych wypisz (w pojedynczym wierszu) liczb całkowitych , gdzie oznacza liczbę min, które wybuchną przy zdetonowaniu -tej miny (wliczając samą -tą minę).

Przykład

Dla danych wejściowych:

poprawną odpowiedzią jest:

4 3 3 3 4

Zadanie zapożyczone z Chicago ACM.