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 java.util.*;
import java.io.*;
import java.lang.Math.*;

public class MainA {

	public static int mod = 20000;
	public static long[] val;
	public static long[] arr;
	static int max = (int) 1e9 + 7;

	static boolean isCyclicUtil(int v, boolean visited[], boolean recStack[], ArrayList adj[])
	{
	    if(visited[v] == false)
	    {
	        // Mark the current node as visited and part of recursion stack
	        visited[v] = true;
	        recStack[v] = true;
	 
	        // Recur for all the vertices adjacent to this vertex
	       
	        for(int i=0;i<adj[v].size();i++)
	        {
	        	int x=(int)adj[v].get(i);
	            if ( !visited[x] && isCyclicUtil(x, visited, recStack,adj) )
	                return true;
	            else if (recStack[x])
	                return true;
	        }
	 
	    }
	    recStack[v] = false;  // remove the vertex from recursion stack
	    return false;
	}
	 
	// Returns true if the graph contains a cycle, else false.
	// This function is a variation of DFS() in https://www.geeksforgeeks.org/archives/18212
	static boolean isCyclic(int V, ArrayList adj[])
	{
	    // Mark all the vertices as not visited and not part of recursion
	    // stack
	    boolean visited[] = new boolean[V];
	    boolean recStack[] = new boolean[V];
	    for(int i = 0; i < V; i++)
	    {
	        visited[i] = false;
	        recStack[i] = false;
	    }
	 
	    for(int i = 0; i < V; i++)
	        if (isCyclicUtil(i, visited, recStack, adj))
	            return true;
	 
	    return false;
	}
	
	
	public static int find(Pairs subsets[], int i)
	{
	    // find root and make root as parent of i (path compression)
	    if (subsets[i].x != i)
	        subsets[i].x = find(subsets, subsets[i].x);
	 
	    return subsets[i].x;
	}
	
	public static void Union(Pairs subsets[], int x1, int y1,int dp[][])
	{
	    int xroot = find(subsets, x1);
	    int yroot = find(subsets, y1);
	 
	    if (subsets[xroot].y < subsets[yroot].y)
	    {
	    	subsets[xroot].x = yroot;
	    	dp[yroot][101]=0;
	    	for(int i=0;i<101;i++)
	    	{
	    		if(dp[xroot][i]==1||dp[yroot][i]==1)
	    		{
	    			dp[yroot][i]=1;
	    			dp[yroot][101]++;
	    		}
	    	}
	    	
	    }
	    else if (subsets[xroot].y > subsets[yroot].y)
	    {
	    	subsets[yroot].x = xroot;
	    	dp[xroot][101]=0;
	    	for(int i=0;i<101;i++)
	    	{
	    		if(dp[yroot][i]==1||dp[xroot][i]==1)
	    		{
	    			dp[xroot][i]=1;
	    			dp[xroot][101]++;
	    		}
	    	}
	    }
	 
	    else
	    {
	        subsets[yroot].x = xroot;
	        subsets[xroot].y++;
	        dp[xroot][101]=0;
	    	for(int i=0;i<101;i++)
	    	{
	    		if(dp[yroot][i]==1||dp[xroot][i]==1)
	    		{
	    			dp[xroot][i]=1;
	    			dp[xroot][101]++;
	    		}
	    	}
	    }
	}

	public static void main(String[] args) {

		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int t=in.nextInt();
		while(t-->0)
		{
			int n=in.nextInt();int time=0;
			for(int i=0;i<n;i++)
			{
				int l=in.nextInt();
				int r=in.nextInt();
				if(i==0)
				{
					out.print(l+" ");
					time=l+1;
				}
				else
				{
					if(time>r)
					{
						out.print(0+" ");
					}
					else
					{
						out.print(Math.max(time,l)+" ");
						time=Math.max(time,l)+1;
					}
				}
			}
			out.println();
			
		}
		out.close();
	}

	static void DFSUtil(int v,boolean visited[],ArrayList adj[],int dp[][],String s)
    {
       
        visited[v] = true;
        //System.out.print(v+" ");
 
        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext())
        {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n,visited,adj,dp,s);
            for(int j=0;j<26;j++)
            {
            	dp[v][j]=Math.max(dp[v][j],dp[n][j]);
            }
        }
        dp[v][s.charAt(v)-'a']++;
    }
 
    // The function to do DFS traversal. It uses recursive DFSUtil()
    static void DFS(int V,ArrayList adj[],int dp[][],String s)
    {
        
        boolean visited[] = new boolean[V];
 
        for (int i=0; i<V; ++i)
            if (visited[i] == false)
                DFSUtil(i, visited,adj,dp,s);
    }
 
	static class Pairs implements Comparable<Pairs> {
		int x;
		int y;

		Pairs(int a, int b) {
			x = a;
			y = b;
		}

		@Override
		public int compareTo(Pairs o) {
			// TODO Auto-generated method stub
			if (x == o.x)
				return Integer.compare(y, o.y);
			else
				return Long.compare(x, o.x);
		}
		
		@Override
		public boolean equals(Object o)
		{
			Pairs other=(Pairs)o;
			return x==other.x && y==other.y;
		}
		
		@Override 
		public int hashCode()
		{
			return Objects.hash(x,y);
		}

	}

	public static void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	public static boolean isPal(String s) {
		for (int i = 0, j = s.length() - 1; i <= j; i++, j--) {
			if (s.charAt(i) != s.charAt(j))
				return false;
		}
		return true;
	}

	public static String rev(String s) {
		StringBuilder sb = new StringBuilder(s);
		sb.reverse();
		return sb.toString();
	}

	public static long gcd(long x, long y) {
		if (y == 0)
			return x;
		if (x % y == 0)
			return y;
		else
			return gcd(y, x % y);
	}

	public static int gcd(int x, int y) {
		if (x % y == 0)
			return y;
		else
			return gcd(y, x % y);
	}

	public static long gcdExtended(long a, long b, long[] x) {

		if (a == 0) {
			x[0] = 0;
			x[1] = 1;
			return b;
		}
		long[] y = new long[2];
		long gcd = gcdExtended(b % a, a, y);

		x[0] = y[1] - (b / a) * y[0];
		x[1] = y[0];

		return gcd;
	}

	public static int abs(int a, int b) {
		return (int) Math.abs(a - b);
	}

	public static long abs(long a, long b) {
		return (long) Math.abs(a - b);
	}

	public static int max(int a, int b) {
		if (a > b)
			return a;
		else
			return b;
	}

	public static int min(int a, int b) {
		if (a > b)
			return b;
		else
			return a;
	}

	public static long max(long a, long b) {
		if (a > b)
			return a;
		else
			return b;
	}

	public static long min(long a, long b) {
		if (a > b)
			return b;
		else
			return a;
	}

	public static long[][] mul(long a[][], long b[][]) {
		long c[][] = new long[2][2];
		c[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
		c[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
		c[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
		c[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];

		return c;
	}

	public static long[][] pow(long n[][], long p, long m) {
		long result[][] = new long[2][2];
		result[0][0] = 1;
		result[0][1] = 0;
		result[1][0] = 0;
		result[1][1] = 1;

		if (p == 0)
			return result;
		if (p == 1)
			return n;
		while (p != 0) {
			if (p % 2 == 1)
				result = mul(result, n);
			//System.out.println(result[0][0]);
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 2; j++) {
					if (result[i][j] >= m)
						result[i][j] %= m;
				}
			}

			p >>= 1;
			n = mul(n, n);
			// System.out.println(1+" "+n[0][0]+" "+n[0][1]+" "+n[1][0]+" "+n[1][1]);
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 2; j++) {
					if (n[i][j] >= m)
						n[i][j] %= m;
				}
			}
		}
		return result;
	}

	public static long pow(long n, long p) {
		long result = 1;
		if (p == 0)
			return 1;
		if (p == 1)
			return n;
		while (p != 0) {
			if (p % 2 == 1)
				result *= n;
			p >>= 1;
			n *= n;
		}
		return result;
	}

	static class InputReader {

		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int snext() {
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = snext();
			while (isSpaceChar(c)) {
				c = snext();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nextLong() {
			int c = snext();
			while (isSpaceChar(c)) {
				c = snext();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int[] nextIntArray(int n) {
			int a[] = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = nextInt();
			}
			return a;
		}

		public long[] nextLongArray(int n) {
			long a[] = new long[n];
			for (int i = 0; i < n; i++) {
				a[i] = nextInt();
			}
			return a;
		}

		public String readString() {
			int c = snext();
			while (isSpaceChar(c)) {
				c = snext();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = snext();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = snext();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
}