베시는 당신이 수행할 수도 있는 \(N\)개의 작업을 가지고 있다. \((1 \le N \le 2 \times 10^5)\)

\(i\)번째 작업을 수행하기로 했다면, 이 작업은 시각 \(s_i\) 이전 또는 시각 \(s_i\)에 시작해야 하며 완료하는 데 \(t_i\)의 시간이 걸린다. \((0 \le s_i \le 10^{18}, 1 \le t_i \le 10^{18})\)

수행할 수 있는 작업 수의 최댓값을 구하여라. 시간은 시각 \(0\)부터 시작한다. 작업을 하나 시작하면 그 작업을 끝낼 때까지 계속 수행해야 하며, 그동안 다른 작업을 시작할 수 없다.

입력

첫째 줄에 독립적인 테스트 케이스의 수 \(T\)가 주어진다. \((1 \le T \le 10)\)

각 테스트 케이스는 다음과 같은 형식으로 주어진다.

테스트 케이스의 첫째 줄에 \(N\)이 주어진다.

다음 \(N\)개의 줄에는 두 정수 \(s_i\)와 \(t_i\)가 주어진다. 이 중 \(i\)번째 줄에는 \(i\)번째 작업의 정보가 주어진다.

모든 테스트 케이스에서 \(N\)의 합은 \(3 \times 10^5\) 이하이다.

출력

각 테스트 케이스마다 수행할 수 있는 작업 수의 최댓값을 한 줄에 하나씩 출력한다.

예제 입력 1

3
2
1 4
1 2
2
2 3
1 2
3
1 4
2 3
1 2

예제 출력 1

1
2
2

예제 설명 1

첫 번째 테스트 케이스에서는 작업을 하나만 수행할 수 있다. 작업 하나를 완료하고 나면 시각 \(2\) 이후가 되므로, 시각 \(1\) 이전 또는 시각 \(1\)에 시작해야 하는 다른 작업을 시작하기에는 너무 늦다.

두 번째 테스트 케이스에서는 시각 \(0\)에 두 번째 작업을 시작하여 시각 \(2\)에 완료한 다음, 시각 \(2\)에 첫 번째 작업을 시작하여 시각 \(5\)에 완료할 수 있다.

출처

USACO 2024 December Contest, Gold, Problem 3. Job Completion