Polycarp found n segments on the street. A segment with the index i is described by two integers l_i and r_i — coordinates of the beginning and end of the segment, respectively. Polycarp realized that he didn't need all the segments, so he wanted to delete some of them.

Polycarp believes that a set of k segments is good if there is a segment [l_i, r_i] (1 ≤ i ≤ k) from the set, such that it intersects every segment from the set (the intersection must be a point or segment). For example, a set of 3 segments [[1, 4], [2, 3], [3, 6]] is good, since the segment [2, 3] intersects each segment from the set. Set of 4 segments [[1, 2], [2, 3], [3, 5], [4, 5]] is not good.

Polycarp wonders, what is the minimum number of segments he has to delete so that the remaining segments form a good set?

Input

The first line contains a single integer t (1 ≤ t ≤ 2 ⋅ 10^5) — number of test cases. Then t test cases follow.

The first line of each test case contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of segments. This is followed by n lines describing the segments.

Each segment is described by two integers l and r (1 ≤ l ≤ r ≤ 10^9) — coordinates of the beginning and end of the segment, respectively.

It is guaranteed that the sum of n for all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case, output a single integer — the minimum number of segments that need to be deleted in order for the set of remaining segments to become good.

Example

Input


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


Output


0
1
2
0

import java.util.*;
import java.lang.*;
import java.io.*;

public class Virtual {

	public static void main(String[] args) throws Exception {

//			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//			int t = Integer.parseInt(br.readLine());
//			StringBuilder sb = new StringBuilder();
//			while (t-- > 0) {
//				int n = Integer.parseInt(br.readLine());
//				String[] str = (br.readLine()).trim().split(" ");
//				int[] arr = new int[n];
//				for (int i = 0; i < n; i++) {
//					arr[i] = Integer.parseInt(str[i]);
//				}
//			}
//			return;

//		first();
//		sec();
//		third();
//		four();
//		fif();
		six();
	}

	private static void first() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		while (t-- > 0) {
			String[] scn = (br.readLine()).trim().split(" ");
			int n = Integer.parseInt(scn[0]);
			int[] arr = new int[n];
			scn = (br.readLine()).trim().split(" ");
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(scn[i]);
			}
			int i = 0;
			int j = n - 1;
			int count = 0;
			while (i <= j) {
				if (count == 0) {
					sb.append(arr[i] + " ");
					count = 1;
					i++;
				} else {
					sb.append(arr[j] + " ");
					j--;
					count = 0;
				}

			}
			sb.append("\n");

		}
		System.out.println(sb);
		return;
	}

	private static void sec() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		while (t-- > 0) {
			String[] scn = (br.readLine()).trim().split(" ");
			int n = Integer.parseInt(scn[0]);
			String str = br.readLine();
			String pat = "2020";
			int c = str.indexOf(pat);
			if (c == 0 || c == n - 4) {
				sb.append("YES");
			} else {
				int j = 0;
				int i = 0;
				while (j < 4 && i < n) {
					if (str.charAt(i) == pat.charAt(j)) {
						j++;
						i++;
					} else {
						break;
					}
				}
				int k = 3;
				i = n - 1;
				while (j <= k && i >= j) {
					if (str.charAt(i) == pat.charAt(k)) {
						k--;
						i--;
					} else {
						break;
					}
				}
				if (k == j - 1) {
					sb.append("YES");

				} else {
					sb.append("NO");

				}
			}
			sb.append("\n");
		}

		System.out.println(sb);
		return;
	}

	private static void third() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		while (t-- > 0) {
			String[] scn = (br.readLine()).trim().split(" ");
			int n = Integer.parseInt(scn[0]);
			if (n > 45) {
				sb.append("-1");
			} else {
				String ans = "";
				int dig = 9;
				while (n > 0) {
					if (n - dig >= 0) {
						ans = dig + ans;
						n -= dig;
					}
					dig -= 1;
				}
				sb.append(ans);
			}
			sb.append("\n");
		}
		System.out.println(sb);
		return;
	}

	private static void four() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		while (t-- > 0) {
			String[] scn = (br.readLine()).trim().split(" ");
			int n = Integer.parseInt(scn[0]);
			int[] arr = new int[n];
			scn = (br.readLine()).trim().split(" ");
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(scn[i]);
			}
			int pre = 0;
			int op = n - 1;
			for (int i = 0; i < n; i++) {
				int newop = i;
				pre += arr[i];
				int sum = 0;
				int prevj = i + 1;
				int j = i + 1;
				for (j = i + 1; j < n; j++) {
					sum += arr[j];
					if (sum > pre) {
						break;
					}
					if (sum == pre) {
						newop += j - prevj;
						prevj = j + 1;
						sum = 0;
					}
				}
				if (j == n && sum == 0) {
					op = Math.min(op, newop);
					break;
				}
			}
			sb.append(op);
			sb.append("\n");

		}
		System.out.println(sb);
		return;
	}

	private static void fif() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		long p = 1000000007;
		InverseofNumber(p);
		InverseofFactorial(p);
		factorial(p);
		while (t-- > 0) {
			String[] scn = (br.readLine()).trim().split(" ");
			int n = Integer.parseInt(scn[0]);
			int m = Integer.parseInt(scn[1]);
			int k = Integer.parseInt(scn[2]);
			int[] arr = new int[n];
			scn = (br.readLine()).trim().split(" ");
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(scn[i]);
			}
			if (m > n) {
				System.out.println("0");
				continue;
			}
			sort(arr, 0, n - 1);
			int i = 0;
			long ans = 0;
			for (int j = m - 1; j < n; j++) {
				while (i < n && arr[j] - arr[i] > k) {
					i++;
				}
				if (i < n && j - i + 1 >= m) {
					ans += Binomial(j - i, m - 1, p);
					ans %= p;
				}
			}
			System.out.println(ans);
		}
		return;
	}

	static int N = 200001;
	static long[] factorialNumInverse = new long[N + 1];
	static long[] naturalNumInverse = new long[N + 1];
	static long[] fact = new long[N + 1];

	static void InverseofNumber(long p) {
		naturalNumInverse[0] = naturalNumInverse[1] = 1;
		for (int i = 2; i <= N; i++)
			naturalNumInverse[i] = naturalNumInverse[(int) (p % i)] * (p - p / i) % p;
	}

	static void InverseofFactorial(long p) {
		factorialNumInverse[0] = factorialNumInverse[1] = 1;
		for (int i = 2; i <= N; i++)
			factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p;
	}

	static void factorial(long p) {
		fact[0] = 1;
		for (int i = 1; i <= N; i++) {
			fact[i] = (fact[i - 1] * i) % p;
		}
	}

	static long Binomial(long N, long R, long p) {
		long ans = ((fact[(int) N] * factorialNumInverse[(int) R]) % p * factorialNumInverse[(int) (N - R)]) % p;
		return ans;
	}

	private static void six() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		while (t-- > 0) {
			String[] scn = (br.readLine()).trim().split(" ");
			int n = Integer.parseInt(scn[0]);
			pair[] arr = new pair[n];
			int[] start = new int[n];
			int[] end = new int[n];
			for (int i = 0; i < n; i++) {
				scn = (br.readLine()).trim().split(" ");
				start[i] = Integer.parseInt(scn[0]);
				end[i] = Integer.parseInt(scn[1]);
				arr[i] = new pair(start[i], end[i]);
			}
			sort(start, 0, n - 1);
			sort(end, 0, n - 1);
			int count = n - 1;
			for (int i = 0; i < n; i++) {
				int a = lower(end, arr[i].l);
				int b = upper(start, arr[i].r);
				count = Math.min(count, a + n - b);

			}
			sb.append(count + "\n");
		}
		System.out.println(sb);
		return;
	}

	public static int lower(int a[], int x) {
		int l = -1, r = a.length;
		while (l + 1 < r) {
			int m = (l + r) >>> 1;
			if (a[m] >= x)
				r = m;
			else
				l = m;
		}
		return r;
	}

	public static int upper(int[] a, int x) {
		int l = -1, r = a.length;
		while (l + 1 < r) {
			int m = (l + r) >>> 1;
			if (a[m] <= x)
				l = m;
			else
				r = m;
		}
		return l + 1;

	}

	static class pair {
		int l, r;

		pair(int l, int r) {
			this.l = l;
			this.r = r;

		}
	}

	static void merge(int arr[], int l, int m, int r) {
		// Find sizes of two subarrays to be merged
		int n1 = m - l + 1;
		int n2 = r - m;

		/* Create temp arrays */
		int L[] = new int[n1];
		int R[] = new int[n2];

		/* Copy data to temp arrays */
		for (int i = 0; i < n1; ++i)
			L[i] = arr[l + i];
		for (int j = 0; j < n2; ++j)
			R[j] = arr[m + 1 + j];

		/* Merge the temp arrays */

		// Initial indexes of first and second subarrays
		int i = 0, j = 0;

		// Initial index of merged subarry array
		int k = l;
		while (i < n1 && j < n2) {
			if (L[i] <= R[j]) {
				arr[k] = L[i];
				i++;
			} else {
				arr[k] = R[j];
				j++;
			}
			k++;
		}

		/* Copy remaining elements of L[] if any */
		while (i < n1) {
			arr[k] = L[i];
			i++;
			k++;
		}

		/* Copy remaining elements of R[] if any */
		while (j < n2) {
			arr[k] = R[j];
			j++;
			k++;
		}
	}

	// Main function that sorts arr[l..r] using
	// merge()
	static void sort(int arr[], int l, int r) {
		if (l < r) {
			// Find the middle point
			int m = (l + r) / 2;

			// Sort first and second halves
			sort(arr, l, m);
			sort(arr, m + 1, r);

			// Merge the sorted halves
			merge(arr, l, m, r);
		}
	}

}
