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

문제

멸종되어가고 있는 눈 덮인 킬리만자로의 표범을 보호하기 위해, 모 국제기구는 킬리만자로 산 정상을 중심으로 하는, 반경 50km 지역을 자연보호구역으로 지정하였다. 그리고, 사람들이 자연보호구역으로 들어가지 못하도록 폐쇄회로 카메라로 이루어진 감시체계를 구축하였다. 이 감시체계는 각각의 구획을 최소한 한 대 이상의 카메라가 감시하고 있도록 구축되었다. 그리고 카메라가 고장이 날 경우를 대비하여, 충분한 숫자의 예비 카메라를 작동시키고 있다. 하지만 예상외로 카메라가 고장이 나는 빈도가 적었기 때문에, 정부는 카메라의 감시구역이 서로 겹치는 경우를 줄여서, 유지보수를 위한 경비를 절감하려고 한다.

카메라들은 자연보호구역 경계인 반경 50km의 원을 따라 설치되어, 그 경계선을 넘나드는 사람들이 있는지 감시하고 있다. 이 카메라들은 설치된 위치에 따라 서로 다른 감시범위를 가진다. 감시범위는 경계의 최북단을 1번 구획이라 하고, 시계방향을 따라 2, 3, …, 100000구획으로 나뉘어있다. 각 카메라는 어떤 한 구획으로부터 연속된 몇 개의 구획을 감시하고 있다. 각 카메라가 감시하고 있는 구획의 범위들이 주어졌을 때, 모든 구획을 최소한 한 대 이상의 카메라가 감시하기 위해 필요한 카메라의 최소 개수를 계산하시오. 단, 주어지는 모든 테스트 케이스에 대해 답이 존재하지 않는 경우는 없다고 가정하시오.


예시: 각 원호는 한 카메라가 감시하고 있는 범위를 나타낸다.
모든 구획을 최소한 한대 이상의 카메라로 감시하기 위해서는 붉게 표시된 범위를 감시하고 있는 카메라들만 가동시키면 된다.

입력

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫 줄에는 현재 설치되어 있는 카메라의 개수 K (1 ≤ K ≤ 20000)가 주어진다. 각 테스트 케이스의 두 번째 줄부터 K줄에 걸쳐, 각 카메라의 감시범위가 두 개의 양의 정수 p, r (1 ≤ p ,r ≤ 100000)로 주어지며, 이는 p번 구획을 포함하여, 시계방향으로 연속된 r개의 구획을 의미한다. 각 숫자는 공백문자로 구분되어 있다.

출력

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해서 모든 구획을 감시하기 위해 필요한 카메라의 최소 개수를 출력하시오. 

예제 입력

2
6
5000 12000
15000 12000
25000 12000
35000 12000
45000 12000
55000 60000
24
1 11631
11630 15322
70349 26852
26951 810
27760 1097
33356 1470
34825 6076
67674 2685
41700 364
42060 7007
49062 2960
6768 12678
51922 144
52064 42909
94972 3314
98285 1718
148 315
312 6457
19346 14010
38334 8335
46664 10738
57392 10292
97200 2639
99829 1173

예제 출력

5
10

힌트