감시체계

멸종 위기에 놓인, 눈 덮인 킬리만자로의 표범을 보호하려고 한 국제기구가 킬리만자로 산 정상을 중심으로 반경 50km 지역을 자연보호구역으로 지정했다. 그리고 사람들이 보호구역에 들어가지 못하도록 폐쇄회로 카메라로 감시체계를 세웠다. 이 감시체계는 어느 구획이든 카메라가 최소 한 대는 감시하도록 구축했고, 카메라가 고장 날 때를 대비해 예비 카메라도 넉넉히 켜 두었다. 그런데 고장이 예상보다 훨씬 드물어서, 정부는 감시구역이 서로 겹치는 카메라를 줄여 유지보수 비용을 아끼려고 한다.

카메라는 자연보호구역의 경계인 반경 50km의 원을 따라 설치되어, 경계선을 넘나드는 사람이 있는지 감시한다. 설치 위치에 따라 카메라마다 감시범위가 다르다. 경계의 최북단이 1번 구획이고, 시계방향으로 2번, 3번, …, 100000번 구획까지 나뉜다. 100000번 구획 다음은 다시 1번 구획이다. 카메라는 저마다 한 구획에서 시작해 시계방향으로 연속한 몇 개의 구획을 감시한다. 카메라마다 감시하는 구획의 범위가 주어졌을 때, 모든 구획을 카메라 최소 한 대가 감시하려면 카메라가 최소 몇 대 필요한지 구하시오. 주어지는 테스트 케이스 중에 답이 존재하지 않는 경우는 없다고 가정한다.

위 그림에서 원호 하나는 카메라 한 대의 감시범위다. 모든 구획을 최소 한 대 이상의 카메라로 감시하려면 붉게 표시한 범위를 맡은 카메라만 가동하면 된다.

입력은 표준입력으로 받는다. 첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 20$)가 주어진다. 각 테스트 케이스의 첫 줄에는 설치되어 있는 카메라의 개수 $K$ ($1 \le K \le 20000$)가 주어진다. 이어지는 $K$개의 줄에는 카메라 한 대의 감시범위가 양의 정수 $p$, $r$ ($1 \le p, r \le 100000$) 두 개로 주어진다. 이는 $p$번 구획부터 시계방향으로 연속한 $r$개의 구획을 뜻한다. 각 수는 공백으로 구분한다.

출력은 표준출력으로 한다. 각 테스트 케이스마다 모든 구획을 감시하는 데 필요한 카메라의 최소 개수를 한 줄에 하나씩 출력한다.