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.*;
 
/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
    static class node
    {
        int s;
        int e;
        public node(int x, int y){
            s = x;
            e = y;
        }
    }
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		int t = Integer.parseInt(br.readLine());
		while(t-- > 0){
		    int n = Integer.parseInt(br.readLine());
		    ArrayList<node> arr = new ArrayList<node>();
		    HashMap<Integer, Integer> map2 = new HashMap<Integer, Integer>();
		    HashMap<Integer, node> map = new HashMap<Integer, node>();
		    for(int i = 0; i < n; i++){
		        String s[] = (br.readLine()).split(" ");
		        int a = Integer.parseInt(s[0]);
		        int b = Integer.parseInt(s[1]);
		        arr.add(new node(a, b));
		        if(map.containsKey(a)){
		            node n1 = map.get(a);
		            n1.s++;
		            map.put(a, n1);
		        }
		        else map.put(a, new node(1, 0));
		        if(map.containsKey(b)){
		            node n1 = map.get(b);
		            n1.e++;
		            map.put(b, n1);
		        }
		        else map.put(b, new node(0, 1));
		    }
		    ArrayList<Integer> arr2 = new ArrayList<Integer>(map.keySet());
		    Collections.sort(arr2);
		    int z = arr2.size();
		    int posto[] = new int[z];
		    int prec[] = new int[z];
		    posto[z - 1] = map.get(arr2.get(z - 1)).s;
		    prec[0] = map.get(arr2.get(0)).e;
		    map2.put(arr2.get(0), 0);
		    for(int i = 1; i < z; i++){
		        map2.put(arr2.get(i), i);
		        prec[i] = prec[i - 1] + map.get(arr2.get(i)).e;
		    }
		    for(int i = z - 2; i >= 0; i--){
		        posto[i] = posto[i + 1] + map.get(arr2.get(i)).s;
		    }
		    //System.out.println(prec[0]+" "+prec[1]+" "+prec[2]+" "+posto[0]+" "+ posto[1]+" "+posto[2]);
		    int min = n;
		    for(int i = 0; i < n; i++){
		        node q = arr.get(i);
		        int s = map2.get(q.s);
		        int e = map2.get(q.e);
		        int ded = 0;
		        if(s > 0){
		            ded += prec[s - 1];
		        }
		        if(e < z - 1){
		            ded += posto[e + 1];
		        }
		        //System.out.println(ded+" "+s+" "+e);
		        if(ded < min) min = ded;
		    }
		    sb.append(min+"\n");
		}  
		System.out.println(sb);
	}
}