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.beans.IntrospectionException;
import java.io.*;
import java.sql.SQLIntegrityConstraintViolationException;
import java.util.*;
import java.lang.*;
import java.math.*;
import java.text.DecimalFormat;
import java.lang.reflect.Array;
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
public class B {
    public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static long MOD = (long) (1e9 + 7);
    //static int MOD = 998244353;
    static long MOD2 = MOD * MOD;
    static FastReader sc = new FastReader();
    static int pInf = Integer.MAX_VALUE;
    static int nInf = Integer.MIN_VALUE;

    public static void main(String[] args) {
        int test = 1;
        test = sc.nextInt();
        while (test-- > 0) solve();
        out.flush();
        out.close();
    }
    public static void solve() {
        int n = sc.nextInt();
        int[] s = new int[n];
        int[] e = new int[n];
        Pair[] a = new Pair[n];
        for(int i = 0; i < n; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            s[i] = x;
            e[i] = y;
            a[i] = new Pair(x,y);
        }
        ruffleSort(s);
        ruffleSort(e);
        int ans = pInf;
//        out.println(Arrays.toString(s));
//        out.println(Arrays.toString(e));
        for(Pair p:a){
            int l = less(e,p.x);
            int r = more(s,p.y);
            ans = Math.min(ans,n-r+l+1);
        }
        out.println(ans);
    }
    static int less(int[] a,int key){
        int l = -1;
        int r = a.length;
        while(r-l>1){
            int m = l+(r-l)/2;
            if(a[m]<key){
                l = m;
            } else{
                r = m;
            }
        }
        return l;
    }
    static int more(int[] a,int key){
        int l = -1;
        int r = a.length;
        while(r-l>1){
            int m = l+(r-l)/2;
            if(a[m]>key){
                r = m;
            } else{
                l = m;
            }
        }
        return r;
    }
    static long nC2(long n) {
        return add((n * (n - 1)) / 2, 0);
    }
    public static long mul(long a, long b) {
        return ((a % MOD) * (b % MOD)) % MOD;
    }
    public static long add(long a, long b) {
        return ((a % MOD) + (b % MOD)) % MOD;
    }
//PrimeFactors
    public static ArrayList<Long> primeFactors(long n) {
        ArrayList<Long> arr = new ArrayList<>();
        if (n % 2 == 0)
            arr.add((long) 2);
        while (n % 2 == 0)
            n /= 2;
        for (long i = 3; i <= Math.sqrt(n); i += 2) {
            int flag = 0;
            while (n % i == 0) {
                n /= i;
                flag = 1;
            }
            if (flag == 1)
                arr.add(i);
        }
        if (n > 2)
            arr.add(n);
        return arr;
    }

    //Pair Class
    static class Pair implements Comparable<Pair> {
        int x;
        int y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public int compareTo(Pair o) {
            if (this.x == o.x) {
                return (this.y - o.y);
            }
            return (this.x - o.x) ;
        }
    }

    static class TPair implements Comparable<TPair> {
        int l;
        int r;
        long index;

        public TPair(int l, int r, long index) {
            this.l = l;
            this.r = r;
            this.index = index;
        }

        @Override
        public int compareTo(TPair o) {
            if (this.l == o.l) {
                return (this.r - o.r);
            }
            return -1 * (this.l - o.l);
        }
    }

    //nCr
    static long[] facts, factInvs;

    static long exp(long base, long e) {
        if (e == 0) return 1;
        long half = exp(base, e / 2);
        if (e % 2 == 0) return mul(half, half);
        return mul(half, mul(half, base));
    }

    static long modInv(long x) {
        return exp(x, MOD - 2);
    }

    static void precomp() {
        facts = new long[1_000_000];
        factInvs = new long[1_000_000];
        factInvs[0] = facts[0] = 1;
        for (int i = 1; i < facts.length; i++)
            facts[i] = mul(facts[i - 1], i);
        factInvs[facts.length - 1] = modInv(facts[facts.length - 1]);
        for (int i = facts.length - 2; i >= 0; i--)
            factInvs[i] = mul(factInvs[i + 1], i + 1);
    }

    static long nCk(int n, int k) {
        return mul(facts[n], mul(factInvs[k], factInvs[n - k]));
    }

    //Kadane's Algorithm
    static long maxSubArraySum(ArrayList<Long> a) {
        if (a.size() == 0) {
            return 0;
        }
        long max_so_far = a.get(0);
        long curr_max = a.get(0);
        for (int i = 1; i < a.size(); i++) {
            curr_max = Math.max(a.get(i), curr_max + a.get(i));
            max_so_far = Math.max(max_so_far, curr_max);
        }
        return max_so_far;
    }

    //Shuffle Sort
    static final Random random = new Random();

    static void ruffleSort(int[] a) {
        int n = a.length;//shuffle, then sort
        for (int i = 0; i < n; i++) {
            int oi = random.nextInt(n), temp = a[oi];
            a[oi] = a[i];
            a[i] = temp;
        }
        Arrays.sort(a);
    }

    //Merge Sort
    static void merge(long 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 */
        long L[] = new long[n1];
        long R[] = new long[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(long 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);
        }
    }

    //Brian Kernighans Algorithm
    static long countSetBits(long n) {
        if (n == 0) return 0;
        return 1 + countSetBits(n & (n - 1));
    }

    //Factorial
    static long factorial(long n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 6;
        return n * factorial(n - 1);
    }

    //Euclidean Algorithm
    static long gcd(long A, long B) {
        if (B == 0) return A;
        return gcd(B, A % B);
    }

    //Modular Exponentiation
    static long fastExpo(long x, long n) {
        if (n == 0) return 1;
        if ((n & 1) == 0) return fastExpo((x * x) % MOD, n / 2) % MOD;
        return ((x % MOD) * fastExpo((x * x) % MOD, (n - 1) / 2)) % MOD;
    }

    //AKS Algorithm
    static boolean isPrime(long n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (int i = 5; i <= Math.sqrt(n); i += 6)
            if (n % i == 0 || n % (i + 2) == 0) return false;
        return true;
    }

    //Reverse an array
    static <T> void reverse(T arr[], int l, int r) {
        Collections.reverse(Arrays.asList(arr).subList(l, r));
    }

    //Print array
    static void print1d(long arr[]) {
        out.println(Arrays.toString(arr));
    }

    static void print2d(int arr[][]) {
        for (int a[] : arr) out.println(Arrays.toString(a));
    }

    //Sieve of eratosthenes
    static int[] findPrimes(int n) {
        boolean isPrime[] = new boolean[n + 1];
        ArrayList<Integer> a = new ArrayList<>();
        int result[];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i * i <= n; ++i) {
            if (isPrime[i] == true) {
                for (int j = i * i; j <= n; j += i) isPrime[j] = false;
            }
        }
        for (int i = 0; i <= n; i++) if (isPrime[i] == true) a.add(i);
        result = new int[a.size()];
        for (int i = 0; i < a.size(); i++) result[i] = a.get(i);
        return result;

    }

    //Indivisual factors of all nos till n
    static ArrayList<Integer>[] indiFactors(int n) {
        ArrayList<Integer>[] A = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            A[i] = new ArrayList<>();
        }
        int[] sieve = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            if (sieve[i] == 0) {
                for (int j = i; j <= n; j += i)
                    if (sieve[j] == 0) {
                        //sieve[j]=i;
                        A[j].add(i);
                    }
            }
        }
        return A;
    }

    //Segmented Sieve
    static boolean[] segmentedSieve(long l, long r) {
        boolean[] segSieve = new boolean[(int) (r - l + 1)];
        Arrays.fill(segSieve, true);
        int[] prePrimes = findPrimes((int) Math.sqrt(r));
        for (int p : prePrimes) {
            long low = (l / p) * p;
            if (low < l) {
                low += p;
            }
            if (low == p) {
                low += p;
            }
            for (long j = low; j <= r; j += p) {
                segSieve[(int) (j - l)] = false;
            }
        }
        if (l == 1) {
            segSieve[0] = false;
        }
        return segSieve;
    }

    //Euler Totent function
    static long countCoprimes(long n) {
        ArrayList<Long> prime_factors = new ArrayList<>();
        long x = n, flag = 0;
        while (x % 2 == 0) {
            if (flag == 0) prime_factors.add(2L);
            flag = 1;
            x /= 2;
        }
        for (long i = 3; i * i <= x; i += 2) {
            flag = 0;
            while (x % i == 0) {
                if (flag == 0) prime_factors.add(i);
                flag = 1;
                x /= i;
            }
        }
        if (x > 2) prime_factors.add(x);
        double ans = (double) n;
        for (Long p : prime_factors) {
            ans *= (1.0 - (Double) 1.0 / p);
        }
        return (long) ans;
    }

    static long modulo = (long) 1e9 + 7;

    public static long modinv(long x) {
        return modpow(x, modulo - 2);
    }

    public static long modpow(long a, long b) {
        if (b == 0) {
            return 1;
        }
        long x = modpow(a, b / 2);
        x = (x * x) % modulo;
        if (b % 2 == 1) {
            return (x * a) % modulo;
        }
        return x;
    }

    public static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        //it reads the data about the specified point and divide the data about it ,it is quite fast
        //than using direct

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception r) {
                    r.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());//converts string to integer
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (Exception r) {
                r.printStackTrace();
            }
            return str;
        }
    }
}