시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

Jarek dostał na gwiazdkę zestaw kostek domina o różnych wysokościach i ustawił je w rzędzie, stawiając każde na sztorc.

Jeśli Jarek przewróci w prawo domino o wysokości H ustawione na pozycji X, spowoduje to przewrócenie w prawo wszystkich kostek domina ustawionych na pozycjach X+1, X+2, ..., X+H. Analogicznie, jeśli Jarek przewróci w lewo domino o wysokości H ustawione na pozycji X, spowoduje to przewrócenie w lewo wszystkich kostek domina ustawionych na pozycjach X-1, X-2, ..., X-H. Kości przewrócone przez pierwszy element analogicznie przewracają kolejne.

Znając wysokość i pozycję każdej kostki domina oblicz maksymalną liczbę elementów które przewrócą się w wyniku przewrócenia jednej kostki w dowolną stronę. 

입력

W pierwszej linii wejścia znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10 ).

Pierwsza linia pojedynczego zestawu testowego zawiera liczbę naturalną (1 <= N <= 10) oznaczającą liczbę kostek domina w zestawie. W kolejnych N liniach znajdują się po dwie liczby naturalne X i H (1<= XH <= 10) oznaczające pozycję i wysokość kolejnych kostek domina. Pozycje kostek są podane w kolejności rosnącej.

출력

Dla każdego zestawu testowego należy w osobnej linii wypisać maksymalną liczbę kostek domina jaka może zostać przewrócona w wyniku przewrócenia jednego elementu.

예제 입력 1

1
4
1 2
4 1
5 2
7 1

예제 출력 1

3