403228: GYM101081 K Pope's work

Karol Wojtyla was born in Wadowice in 1920. He was elected as pope John Paul II in 1978 and died in April 2th in 2005, after completing 26 years of papacy. He is one of the most important polish men in history.

Before devoting his life to religion, during the World War II, he worked in a factory of chemical products. One of his duties was to arrange boxes containing chemical products in stacks. The problem was that some of these boxes were really heavy, and others could not afford much weight over them. The managers of the factory wanted big stacks, with the highest number of boxes possible. Every box had associated two attributes: its weight (in kilograms) and the weight that it is able to afford in kilograms (including the weight of the box). For example, a box of 25 kg. and 60 kg. of resistance is able to hold at most 35 kg. on top of it.

Your task is, given a list of boxes, along with their weight and resistance, determine the maximum number of boxes that can be arranged into a stack without exceeding the resistance of any of them.

The first line contains an integer T, the number of test cases.

The first line of each test case contains an integer N, the number of boxes. Each of the next N lines contains two integers, the ith has W_i and R_i, the weight and the resistance of box i, respectively.

Limits

• 1 ≤ T ≤ 25
• 1 ≤ N ≤ 10³
• The sum of N over all test cases will not exceed 3·10³
• 1 ≤ W_i ≤ 10³
• W_i ≤ R_i ≤ 10⁶

For each test case, print the maximum number of boxes that can be arrange into a stack.

2
4
13 30
11 15
7 28
6 6
3
43 60
47 100
430 450

3
2