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