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.io.*;
import java.math.*;
public class C{
	static long mod = (long)1e9+7;
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	public static void main(String[] args)throws IOException {
		FastReader sc = new FastReader();
		//Scanner sc = new Scanner(System.in);

		int t = sc.nextInt();
		while(t-->0){
			int n = sc.nextInt();
			ArrayList<pair> al = new ArrayList<>();
			PriorityQueue<pair> pr = new PriorityQueue<>(new desc());
			for(int i=0;i<n;i++){
				al.add(new pair(sc.nextInt(), sc.nextInt()));
			}
			Collections.sort(al, new asc());
			
			long ans = 0;
			for(int i=0;i<n;i++){
				pair op = al.get(i);
				long cnt = 1;
				cnt += search(op.r,i+1,  al);
				
				while(pr.size()>0){
					pair pp = pr.peek();
					if(pp.r<op.l){
						pr.poll();
					}else{
						break;
					}
				}
				cnt += pr.size();
				ans = Math.max(ans, cnt);
				pr.add(al.get(i));
			}
			System.out.println(n-ans);
		}
	}
		
	public static int search(int val, int l ,ArrayList<pair> al){
		
		int r = al.size()-1;
		int pp = l;
		int ans = 0;
		while(l<=r){
			int mid = (l+r)/2;
			if(al.get(mid).l<=val){
				ans = Math.max(ans, mid-pp+1);
				l = mid+1;
			}else{
				r = mid-1;
			}
		}
		return ans;
	}
	
	static class pair{
		int l;
		int r;
		pair(int a, int b){
			l = a;
			r = b;
		}
	}
	
	static class asc implements Comparator<pair>{
		public int compare(pair o1, pair o2){
			if(o1.l==o2.l)
				return o1.r-o2.r;
			return o1.l-o2.l;
		}
	}
	
	static class desc implements Comparator<pair>{
		public int compare(pair o1, pair o2){
			return o1.r-o2.r;
		}
	}









	static ArrayList<Integer> factor(int n){
		ArrayList<Integer> hm = new ArrayList<>();
		int sqrt = (int)Math.sqrt(n);
		for(int i=1;i<=sqrt;i++){
			if(n%i==0){
				hm.add(i);
				if(n/i!=i)
					hm.add(n/i);
			}
		}
		return hm;
	}

	public static boolean prime(long n){
		for(long i=2;i*i<=n;i++){
			if(n%i==0)
				return false;
		}
		return true;
	}

	public static long power(long a, long b){

		long temp = 0l;
		if(b==0)
			return 1l;

		temp = power(a, b/2);
		if(b%2==0)
			return (temp%mod*temp%mod)%mod;
		return (a%mod*(temp%mod*temp%mod)%mod)%mod;
	}

	public static ArrayList<Integer> primefactor(int n){
		int sqrt = (int)Math.sqrt(n);
		ArrayList<Integer> al = new ArrayList<>();
		while(n%2==0){
			al.add(2);
			n/=2;
		}
		for(int i=3;i<=sqrt;i+=2){
			while(n%i==0){
				al.add(i);
				n/=i;
			}
		}
		if(n>2)
			al.add(n);
		return al;
	}

	public static long sum(long val){
		long fg =0 ;
		while(val!=0){
			fg+=val%10;
			val/=10;
		}
		return fg;
	}




	static int sum(ArrayList<Integer> v){
		int n = v.size();
		int cs= 0;
		int gs = 0;
		for(int i=0;i<n;i++){
			if(v.get(i)>=0){
				cs+=v.get(i);
				gs = Math.max(cs,gs);
			}
			else if(v.get(i)<0){
				cs = 0;
			}
		}
		return gs;
	}




	public static ArrayList<Integer> comp(){
		ArrayList<Integer> al = new ArrayList<>();
			int n = (int)2e5;
			boolean arr[] = new boolean[n+1];
			int sqrt = (int)Math.sqrt(n);
			for(int i=2;i<=sqrt;i++){
				if(arr[i]==false){
					for(int j=i*i;j<=n;j+=i){
						arr[j]=true;
					}
				}
			}
			for(int i=2;i<=n;i++){
				if(arr[i]==false)
					al.add(i);
			}

		return al;
	}






	static int gcd(int a, int b)
    {
      if (b == 0)
        return a;
      return gcd(b, a % b);
    }


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

		public FastReader()
		{
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public FastReader(String file_name) throws IOException
		{
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readLine() throws IOException
		{
			byte[] buf = new byte[64]; // line length
			int cnt = 0, c;
			while ((c = read()) != -1)
			{
				if (c == '\n')
					break;
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}

		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
		{
			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++];
		}

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