Recently n students from city S moved to city P to attend a programming camp.

They moved there by train. In the evening, all students in the train decided that they want to drink some tea. Of course, no two people can use the same teapot simultaneously, so the students had to form a queue to get their tea.

i-th student comes to the end of the queue at the beginning of li-th second. If there are multiple students coming to the queue in the same moment, then the student with greater index comes after the student with lesser index. Students in the queue behave as follows: if there is nobody in the queue before the student, then he uses the teapot for exactly one second and leaves the queue with his tea; otherwise the student waits for the people before him to get their tea. If at the beginning of ri-th second student i still cannot get his tea (there is someone before him in the queue), then he leaves the queue without getting any tea. 

For each student determine the second he will use the teapot and get his tea (if he actually gets it).

Input

The first line contains one integer t — the number of test cases to solve (1 ≤ t ≤ 1000).

Then t test cases follow. The first line of each test case contains one integer n (1 ≤ n ≤ 1000) — the number of students.

Then n lines follow. Each line contains two integer li, ri (1 ≤ li ≤ ri ≤ 5000) — the second i-th student comes to the end of the queue, and the second he leaves the queue if he still cannot get his tea.

It is guaranteed that for every <image> condition li - 1 ≤ li holds.

The sum of n over all test cases doesn't exceed 1000.

Note that in hacks you have to set t = 1.

Output

For each test case print n integers. i-th of them must be equal to the second when i-th student gets his tea, or 0 if he leaves without tea.

Example

Input

2
2
1 3
1 4
3
1 5
1 1
2 3


Output

1 2 
1 0 2 

Note

The example contains 2 tests:

  1. During 1-st second, students 1 and 2 come to the queue, and student 1 gets his tea. Student 2 gets his tea during 2-nd second. 
  2. During 1-st second, students 1 and 2 come to the queue, student 1 gets his tea, and student 2 leaves without tea. During 2-nd second, student 3 comes and gets his tea. 
import sun.reflect.generics.tree.Tree;

import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;
import java.util.Map.Entry;

public class Template {

    class Edge{
        int to;
        int num;
        Edge(int to, int num){
            this.to = to;
            this.num = num;
        }
    }

    class Vertex{
        int x, y;
        Vertex(int x, int y){
            this.x = x;
            this.y = y;
        }

    }
    String fileName = "";
    int MODULO = 1000*1000*1000+7;
    ArrayList<Integer>[] graph;
    char[] s;
    int[] colors;
    boolean cycle = false;
    int ans = 0;
    int[] count = new int[26];
    class Student implements Comparable<Student>{
        int num, l, r;
        Student(int num, int l, int r){
            this.num = num;
            this.l = l;
            this.r = r;
        }

        @Override
        public int compareTo(Student o) {
            if(this.l == o.l){
                return Integer.compare(this.num, o.num);
            }
            return Integer.compare(this.l, o.l);
        }
    }
    void solve() throws IOException {
        int t = readInt();
        for(int q=0; q<t; ++q){
            int n = readInt();
            Student[] students = new Student[n];
            int[] ans = new int[n];

            for(int i=0; i<n; ++i){
                students[i] = new Student(i, readInt(), readInt());
            }
            int curTime = 1;
            for(int i=0; i<n; ++i){
                if(students[i].r>=curTime){
                    ans[students[i].num] = Math.max(students[i].l, curTime);
                    curTime = Math.max(students[i].l + 1, curTime+1);

                }else{
                    ans[students[i].num] = 0;
                }

            }
            for(int i=0; i<n; ++i){
                out.print(ans[i]+" ");
            }
            out.println();
        }
    }


    ////////////////////////////////////////////////////////////
    class Pair{
        int num;
        int val;
        Pair(int num, int val ){
            this.num = num;
            this.val = val;
        }
    }
    class SegmentTree {
        int[] t;
        int[] nums;
        SegmentTree(int[] a) {
            int n = a.length - 1;
            t = new int[n * 4];
            nums = new int[n*4];
            build(a, 1, 1, n);
        }
        Pair max1;
        Pair max2;
        void build(int[] a, int v, int tl, int tr) {
            if (tl == tr) {
                t[v] = a[tl];
                nums[v] = tl;
                return;
            }

            int mid = (tr + tl) / 2;

            build(a, 2 * v, tl, mid);
            build(a, 2 * v + 1, mid + 1, tr);

            t[v] = Math.max(t[2 * v], t[2 * v + 1]);
            if(t[v] == t[2*v]){
                nums[v] = nums[2*v];
            }else{
                nums[v] = nums[2*v+1];
            }
        }

        void update(int v, int tl, int tr, int pos, int value) {
            if (tl == tr) {
                t[v] = value;
                return;
            }

            int mid = (tl + tr) / 2;

            if (pos <= mid) {
                update(2 * v, tl, mid, pos, value);
            } else {
                update(2 * v + 1, mid + 1, tr, pos, value);
            }

            t[v] = Math.max(t[2 * v], t[2 * v + 1]);
            if(t[v] == t[2*v]){
                nums[v] = nums[2*v];
            }else{
                nums[v] = nums[2*v+1];
            }
        }

        Pair getMax(int v, int tl, int tr, int l, int r) {
            if (l > r) {
                return new Pair(-1,-1000 * 1000);
            }
            if (tl == tr) {
                return new Pair(nums[v],t[v]);
            }

            if (l == tl && r == tr) {
                return new Pair(nums[v],t[v]);
            }

            int mid = (tl + tr) / 2;

            max1 = getMax(2 * v, tl, mid, l, Math.min(mid, r));
            max2 = getMax(2 * v + 1, mid + 1, tr, Math.max(mid + 1, l), r);

            int max = Math.max(max1.val, max2.val);
            if(max1.val == max){
                return max1;
            }else{
                return max2;
            }
        }
    }
    class Fenwik {
        long[] t;
        int length;

        Fenwik(int[] a) {
            length = a.length + 100;
            t = new long[length];

            for (int i = 0; i < a.length; ++i) {
                inc(i, a[i]);
            }
        }

        void inc(int ind, int delta) {
            for (; ind < length; ind = ind | (ind + 1)) {
                t[ind] += delta;
            }
        }

        long getSum(int r) {
            long sum = 0;
            for (; r >= 0; r = (r & (r + 1)) - 1) {
                sum += t[r];
            }
            return sum;
        }
    }
    int gcd(int a, int b){
        return b == 0 ? a : gcd(b, a%b);
    }

    long binPow(long a, long b, long m) {
        if (b == 0) {
            return 1;
        }
        if (b % 2 == 1) {
            return ((a % m) * (binPow(a, b - 1, m) % m)) % m;
        } else {
            long c = binPow(a, b / 2, m);
            return (c * c) % m;
        }

    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        new Template().run();
    }

    void run() throws NumberFormatException, IOException {
        solve();
        out.close();
    };

    BufferedReader in;
    PrintWriter out;

    StringTokenizer tok;
    String delim = " ";
    Random rnd = new Random();

    Template() throws FileNotFoundException {
        try {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        } catch (Exception e) {
            if (fileName.isEmpty()) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader(fileName + ".in"));
                out = new PrintWriter(fileName + ".out");
            }

        }
        tok = new StringTokenizer("");
    }

    String readLine() throws IOException {
        return in.readLine();
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            String nextLine = readLine();
            if (null == nextLine) {
                return null;
            }

            tok = new StringTokenizer(nextLine);
        }
        return tok.nextToken();
    }

    int readInt() throws NumberFormatException, IOException {
        return Integer.parseInt(readString());
    }
    byte readByte() throws NumberFormatException, IOException {
        return Byte.parseByte(readString());
    }
    int[] readIntArray (int n) throws NumberFormatException, IOException {
        int[] a = new int[n];
        for(int i=0; i<n; ++i){
            a[i] = readInt();
        }
        return a;
    }
    long readLong() throws NumberFormatException, IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws NumberFormatException, IOException {
        return Double.parseDouble(readString());
    }
}