C. Void's Batteries
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two arrays $$$charge$$$ and $$$capacity$$$, both of size $$$n$$$, where $$$charge_i$$$ represents the initial amount of charge in battery $$$i$$$, and $$$capacity_i$$$ represents its maximum capacity ($$$0 \le charge_i \le capacity_i$$$).

You can perform the following operation any number of times (possibly zero):

  • Transfer $$$1$$$ integer unit of charge from battery $$$i$$$ to battery $$$j$$$ ($$$i \neq j$$$).

You cannot transfer charge into a battery if it would cause its charge to exceed its capacity.

Find the maximum possible number of fully charged batteries.

Note: A battery is fully charged when its charge is equal to its capacity.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of batteries.

The following $$$n$$$ lines each contain two integers $$$charge_i$$$ and $$$capacity_i$$$ ($$$0 \le charge_i \le capacity_i \le 10^9$$$) — the initial charge and capacity of the $$$i$$$-th battery.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the maximum possible number of fully charged batteries after performing the operations optimally.

Example
Input
3
3
1 4
2 3
1 5
5
5 6
5 6
5 6
5 6
5 6
1
13 1000000000
Output
1
4
0