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
#include<bits/stdc++.h>
  using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

  #define int long long int
  #define endl "\n"
  #define MOD 1000000007
  #define mod 1000000007
  #define M 1000000007
  #define pb push_back
  #define take(a,b,c) for(int b=0;b<c;b++) cin>>a[b]
  #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  #define mx 400005
  #define fiint(a,b) memset(a,b,sizeof(a))
  #define bitcount __builtin_popcount
  #define fori(i,a,b) for(int i=a;i<b;i++)
  #define ford(i,a,b) for(int i=a;i>=b;i--)
  #define debug(x) cout<<x<<endl;
  #define cases(t) int t; cin>>t; while(t--)
  #define inf1 INT_MAX
  #define all(a) a.begin(),a.end()
  #define vec vector<int>
  #define pii pair<int,int>
  #define plii pair<int,int>
  #define pint pair<int,int>
  #define ff first
  #define ss second
  #define lb lower_bound
  #define ub upper_bound
  #define bs binary_search
  #define mp make_pair

#define sz(x) (int)x.size()
#define PI    3.14159265359


vector<int> tree[8*100005];
vector<pair<int,int>> v;
void build(int node , int st,int en)
{
    tree[node].clear();
    if(st == en)
    {
        tree[node].pb(v[st].ss);
        return ;
    }
    int mid = (st + en)/2;
    build(2*node , st,mid);
    build(2*node + 1, mid+1,en);
    int l = 0 ,  r = 0;
    while(l < tree[2*node].size() && r < tree[2*node + 1].size())
    {
        if( tree[2*node][l] < tree[2*node+1][r] )
        {       tree[node].pb(tree[2*node][l++]);     }
        else
        { tree[node].pb(tree[2*node+1][r++]);}
    }

    while(l < tree[2*node].size() )
    {
      tree[node].pb(tree[2*node][l++]);
    }

    while( r < tree[2*node + 1].size())
    {
        tree[node].pb(tree[2*node+1][r++]);
    }
    return ;
}

int query(int node , int st,int en ,int l ,int r,int val)
{
    if( st > r || en < l   )
    return  0;
    if(st >= l  && r >= en )
    {
        int c =  lb(all(tree[node]) ,  val ) - tree[node].begin();
        return c;
    }
    int mid = (st + en)/2;
    return query(2*node , st , mid , l ,r,val) + query(2*node +1 , mid + 1,en , l ,r,val);
}

signed  main()
{
  boost
  cases(t)
  {
    int n;cin>>n;
    v.clear();
    for(int i = 0 ; i < n ;i++)
    { int a,b;cin>>a>>b;   v.pb(mp(a,b));}
    sort(all(v));
    build(1,0,n-1);
    int ans = INT_MAX  ;
    for(int i = 0 ; i < n ;i++)
    {
        int a = lb(all(v) , mp(v[i].ss + 1 , v[i].ss + 1)) - v.begin();
       int b = query(1,0,n-1,0,i-1,v[i].ff);
       ans = min(ans , n- a+b);
    }
    cout<<ans<<endl;


  }
}
