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.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Objects;
import java.util.StringTokenizer;

public class CodeforceTemplate {

  private static FastScanner scanner = new FastScanner();
  private static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
  private static final int MOD = 1_000_000_007;

  public static void main(String[] args) {
    int tests = rInt();
    for (int i = 0; i < tests; i++) {
      solve();
    }
  }

  private static void solve() {
    int n = rInt();
    List<Integer> ls = new ArrayList<>();
    List<Integer> rs = new ArrayList<>();
    List<List<Integer>> segments = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      int l = rInt();
      ls.add(l);
      int r = rInt();
      rs.add(r);
      segments.add(Arrays.asList(l, r));
    }
    Collections.sort(ls);
    Collections.sort(rs);
    int best = n - 1;
    for (int i = 0; i < n; i++) {
      List<Integer> segment = segments.get(i);
      int from = findSmaller(rs, segment.get(0) - 1) + 1;
      int to = n - findLarger(ls, segment.get(1) + 1);
      best = Math.min(best, from + to);
    }
    wl(best);
  }

  private static int findLarger(List<Integer> a, int target) {
    int l = 0, r = a.size() - 1;
    int ans = a.size();
    while (l <= r) {
      int mid = (l + r) / 2;
      if (a.get(mid) >= target) {
        ans = mid;
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    return ans;
  }

  private static int findSmaller(List<Integer> a, int target) {
    int l = 0, r = a.size() - 1;
    int ans = -1;
    while (l <= r) {
      int mid = (l + r) / 2;
      if (a.get(mid) <= target) {
        ans = mid;
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    return ans;
  }

//  static long rangeMultiplier(long from, long to) {
//    long res = 1;
//    while (from <= to) {
//      res = (res * from) % MOD;
//      from++;
//    }
//    return res;
//  }

//  int n = rInt();
//  int m = rInt(); // element count
//  int k = rInt(); // max diff
//  int[] a = rIntArr(n);
//  FenwickTree fenwick = new FenwickTree(new int[20005]);
//  long result = 0;
//    for (int i = 0; i < a.length; i++) {
//    int curr = a[i];
//    int total = fenwick.sum(Math.min(0, curr - k), curr);
//    if (total >= m) {
//      long increment = rangeMultiplier(total - m, total);
//      result = (result + increment) % MOD;
//    }
//    fenwick.inc(curr, 1);
//  }
//  wl(result);


  private static final int[][] DIRS_2D = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

  private final static class FastScanner {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer("");

    String next() {
      while (!st.hasMoreTokens()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

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

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

    int[] readIntArray(int size) {
      int[] arr = new int[size];
      for (int i = 0; i < size; i++) {
        arr[i] = scanner.nextInt();
      }
      return arr;
    }

    long[] readLongArray(int size) {
      long[] arr = new long[size];
      for (int i = 0; i < size; i++) {
        arr[i] = scanner.nextLong();
      }
      return arr;
    }
  }

  private static void wl(String ans) {
    try {
      out.write(ans);
      out.newLine();
      out.flush();
    } catch (IOException e) {
      e.printStackTrace();
    }
  }

  private static void wl(double ans) {
    wl(String.valueOf(ans));
  }

  private static void wl(long ans) {
    wl(String.valueOf(ans));
  }

  private static void wl(int ans) {
    wl(String.valueOf(ans));
  }

  private static double rDouble() {
    return scanner.nextDouble();
  }


  private static int rInt() {
    return scanner.nextInt();
  }

  private static long rLong() {
    return scanner.nextLong();
  }

  private static String rStr() {
    return scanner.next();
  }

  private static int[] rIntArr(int size) {
    return scanner.readIntArray(size);
  }

  private static long[] rLongArr(int size) {
    return scanner.readLongArray(size);
  }

  private static class Pair<U, V> implements Comparable<Pair<U, V>> {

    final U first;
    final V second;

    static <U, V> Pair<U, V> makePair(U first, V second) {
      return new Pair<U, V>(first, second);
    }

    private Pair(U first, V second) {
      this.first = first;
      this.second = second;
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) {
        return true;
      }
      if (o == null || getClass() != o.getClass()) {
        return false;
      }

      Pair pair = (Pair) o;

      return Objects.equals(first, pair.first) &&
          Objects.equals(second, pair.second);
    }

    @Override
    public int hashCode() {
      int result = first != null ? first.hashCode() : 0;
      result = 31 * result + (second != null ? second.hashCode() : 0);
      return result;
    }

    public Pair<V, U> swap() {
      return makePair(second, first);
    }

    @Override
    public String toString() {
      return "(" + first + "," + second + ")";
    }

    @SuppressWarnings({"unchecked"})
    public int compareTo(Pair<U, V> o) {
      int value = ((Comparable<U>) first).compareTo(o.first);
      if (value != 0) {
        return value;
      }
      return ((Comparable<V>) second).compareTo(o.second);
    }
  }

  private static class FenwickTree {

    private final int n;
    private final int[] tree;
    private final int[] values;

    FenwickTree(int[] arr) {
      this.n = arr.length;
      this.values = Arrays.copyOf(arr, arr.length);
      this.tree = new int[n + 1];
      for (int i = 1; i <= n; i++) {
        inc(i, values[i - 1]);
      }
    }

    int sum(int l, int r) {
      return read(r) - read(l + 1);
    }

    int read(int idx) {
      int sum = 0;
      while (idx > 0) {
        sum += tree[idx];
        idx -= (idx & -idx);
      }
      return sum;
    }

    void inc(int idx, int val) {
      while (idx <= n) {
        tree[idx] += val;
        idx += (idx & -idx);
      }
    }

    void update(int idx, int val) {
      int delta = val - values[idx - 1];
      if (delta != 0) {
        values[idx - 1] += delta;
        inc(idx, delta);
      }
    }

  }
}