You are given $N$ items with their price ($P_i$) and value ($V_i$).

You are required to choose a subset of items such that (size of subset + sum of values of all selected elements)$\ge$$N$ and the sum of prices of all selected elements must be minimum.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains an integer $N$ denoting the number of $N$ items.
• Each of the next $N$ lines contain two space-separated integers $V_i$ and $P_i$.

Output format

For each test case, print a single line denoting the minimum value of the sum of prices of selected elements.

Constraints

• $1\leq T \leq 100$
• $1 \leq N \leq 1000$
• $0 \leq V_i \leq N$
• $1 \leq P_i \leq 10^9$
• Sum of N over all test cases will not exceed 2000