The only difference between easy and hard versions is constraints.

Now elections are held in Berland and you want to win them. More precisely, you want everyone to vote for you.

There are n voters, and two ways to convince each of them to vote for you. The first way to convince the i-th voter is to pay him p_i coins. The second way is to make m_i other voters vote for you, and the i-th voter will vote for free.

Moreover, the process of such voting takes place in several steps. For example, if there are five voters with m_1 = 1, m_2 = 2, m_3 = 2, m_4 = 4, m_5 = 5, then you can buy the vote of the fifth voter, and eventually everyone will vote for you. Set of people voting for you will change as follows: {5} → {1, 5} → {1, 2, 3, 5} → {1, 2, 3, 4, 5}.

Calculate the minimum number of coins you have to spend so that everyone votes for you.

Input

The first line contains one integer t (1 ≤ t ≤ 5000) — the number of test cases.

The first line of each test case contains one integer n (1 ≤ n ≤ 5000) — the number of voters.

The next n lines contains the description of voters. i-th line contains two integers m_i and p_i (1 ≤ p_i ≤ 10^9, 0 ≤ m_i < n).

It is guaranteed that the sum of all n over all test cases does not exceed 5000.

Output

For each test case print one integer — the minimum number of coins you have to spend so that everyone votes for you.

Example

Input


3
3
1 5
2 10
2 8
7
0 1
3 1
1 1
6 1
1 1
4 1
4 1
6
2 6
2 3
2 8
2 7
4 4
5 5


Output


8
0
7

Note

In the first test case you have to buy vote of the third voter. Then the set of people voting for you will change as follows: {3} → {1, 3} → {1, 2, 3}.

In the second example you don't need to buy votes. The set of people voting for you will change as follows: {1} → {1, 3, 5} → {1, 2, 3, 5} → {1, 2, 3, 5, 6, 7} → {1, 2, 3, 4, 5, 6, 7}.

In the third test case you have to buy votes of the second and the fifth voters. Then the set of people voting for you will change as follows: {2, 5} → {1, 2, 3, 4, 5} → {1, 2, 3, 4, 5, 6}.

import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class E {

	public static void main(String[] args) throws Exception {
		FastScanner sc = new FastScanner(System.in);
		FastPrinter out = new FastPrinter(System.out);
		E runner = new E();
		int T = sc.nextInt();
		for (int t = 0; t < T; t++) {
			runner.run(sc, out);
		}
		out.close();
	}

	public void run(FastScanner sc, FastPrinter out) throws Exception {
		int N = sc.nextInt();
		int[][] arr = new int[N][2];
		for (int i = 0; i < arr.length; i++) {
			arr[i][0] = sc.nextInt();
			arr[i][1] = sc.nextInt();
		}
		for (int i = 0; i < N; i++) {
			int[] temp = arr[i];
			int rand = (int) (Math.random());
			arr[i] = arr[rand];
			arr[rand] = temp;
		}
		Arrays.sort(arr, new Comparator<int[]>() {

			@Override
			public int compare(int[] a, int[] b) {
				int diff = a[0] - b[0];
				if (diff == 0) {
					return a[1] - b[1];
				}
				return diff;
			}

		});
		// for (int i = 0; i < N; i++) {
		// System.out.println(Arrays.toString(arr[i]));
		// }
		long cost = 0;
		int bought = 0;
		PriorityQueue<Integer> costs = new PriorityQueue<>();
		for (int i = N - 1; i >= 0; i--) {
			int[] cur = arr[i];
			costs.add(cur[1]);
			if (cur[0] - bought > i) {
				bought++;
				cost += costs.poll();
			}
		}
		System.out.println(cost);
		// System.out.println(people);
		// System.out.println(boughtM.size());
	}

	public void shuffle(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			int r = (int) (Math.random() * arr.length);
			if (i != r) {
				arr[i] ^= arr[r];
				arr[r] ^= arr[i];
				arr[i] ^= arr[r];
			}
		}
	}

	static class FastScanner {
		final private int BUFFER_SIZE = 1 << 10;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public FastScanner() {
			this(System.in);
		}

		public FastScanner(InputStream stream) {
			din = new DataInputStream(stream);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public FastScanner(String fileName) throws IOException {
			Path p = Paths.get(fileName);
			buffer = Files.readAllBytes(p);
			bytesRead = buffer.length;
		}

		int[] nextIntArray(int N) throws IOException {
			int[] arr = new int[N];
			for (int i = 0; i < N; i++) {
				arr[i] = nextInt();
			}
			return arr;
		}

		String nextLine() throws IOException {
			int c = read();
			while (c != -1 && isEndline(c))
				c = read();
			if (c == -1) {
				return null;
			}
			StringBuilder res = new StringBuilder();
			do {
				if (c >= 0) {
					res.appendCodePoint(c);
				}
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		String next() throws Exception {
			int c = readOutSpaces();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg) c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg) return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg) c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg) return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg) c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg) return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			if (din == null) {
				bufferPointer = 0;
				bytesRead = -1;
			} else {
				bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			}
			if (bytesRead == -1) buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead) fillBuffer();
			return buffer[bufferPointer++];
		}

		private int readOutSpaces() throws IOException {
			while (true) {
				if (bufferPointer == bytesRead) fillBuffer();
				int c = buffer[bufferPointer++];
				if (!isSpaceChar(c)) {
					return c;
				}
			}
		}

		public void close() throws IOException {
			if (din == null) return;
			din.close();
		}

		public int[][] readGraph(int N, int M, boolean zeroIndexed, boolean bidirectional) throws Exception {
			int[][] adj = new int[N][];
			int[] numNodes = new int[N];
			int[][] input = new int[M][2];
			for (int i = 0; i < M; i++) {
				int a = nextInt();
				int b = nextInt();
				if (zeroIndexed) {
					a--;
					b--;
				}
				input[i][0] = a;
				input[i][1] = b;
				numNodes[a]++;
				if (bidirectional) numNodes[b]++;
			}
			for (int i = 0; i < N; i++) {
				adj[i] = new int[numNodes[i]];
				numNodes[i] = 0;
			}
			for (int i = 0; i < M; i++) {
				int a = input[i][0];
				int b = input[i][1];
				adj[a][numNodes[a]++] = b;
				if (bidirectional) adj[b][numNodes[b]++] = a;
			}
			return adj;
		}

		public int[][][] readWeightedGraph(int N, int M, boolean zeroIndexed, boolean bidirectional) throws Exception {
			int[][][] adj = new int[N][][];
			int[] numNodes = new int[N];
			int[][] input = new int[M][3];
			for (int i = 0; i < M; i++) {
				int a = nextInt();
				int b = nextInt();
				if (zeroIndexed) {
					a--;
					b--;
				}
				int d = nextInt();
				input[i][0] = a;
				input[i][1] = b;
				input[i][2] = d;
				numNodes[a]++;
				if (bidirectional) numNodes[b]++;
			}
			for (int i = 0; i < N; i++) {
				adj[i] = new int[numNodes[i]][2];
				numNodes[i] = 0;
			}
			for (int i = 0; i < M; i++) {
				int a = input[i][0];
				int b = input[i][1];
				int d = input[i][2];
				adj[a][numNodes[a]][0] = b;
				adj[a][numNodes[a]][1] = d;
				numNodes[a]++;
				if (bidirectional) {
					adj[b][numNodes[b]][0] = a;
					adj[b][numNodes[b]][1] = d;
					numNodes[b]++;
				}
			}
			return adj;
		}
	}

	static class FastPrinter {
		static final char ENDL = '\n';
		StringBuilder buf;
		PrintWriter pw;

		public FastPrinter(OutputStream stream) {
			buf = new StringBuilder();
			pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(stream)));
		}

		public FastPrinter(String fileName) throws Exception {
			buf = new StringBuilder();
			pw = new PrintWriter(new BufferedWriter(new FileWriter(fileName)));
		}

		public FastPrinter(StringBuilder buf) {
			this.buf = buf;
		}

		public void print(int a) {
			buf.append(a);
		}

		public void print(long a) {
			buf.append(a);
		}

		public void print(char a) {
			buf.append(a);
		}

		public void print(char[] a) {
			buf.append(a);
		}

		public void print(double a) {
			buf.append(a);
		}

		public void print(String a) {
			buf.append(a);
		}

		public void print(Object a) {
			buf.append(a.toString());
		}

		public void println() {
			buf.append(ENDL);
		}

		public void println(int a) {
			buf.append(a);
			buf.append(ENDL);
		}

		public void println(long a) {
			buf.append(a);
			buf.append(ENDL);
		}

		public void println(char a) {
			buf.append(a);
			buf.append(ENDL);
		}

		public void println(char[] a) {
			buf.append(a);
			buf.append(ENDL);
		}

		public void println(double a) {
			buf.append(a);
			buf.append(ENDL);
		}

		public void println(String a) {
			buf.append(a);
			buf.append(ENDL);
		}

		public void println(Object a) {
			buf.append(a.toString());
			buf.append(ENDL);
		}

		public void printf(String format, Object... args) {
			buf.append(String.format(format, args));
		}

		public void close() {
			pw.print(buf);
			pw.close();
		}

		public void flush() {
			pw.print(buf);
			pw.flush();
			buf.setLength(0);
		}

	}

}