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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.PriorityQueue;
				public class Solution1 implements Runnable
				{
					static final long MAX = 1000000007L;
					static class InputReader
					{
						private InputStream stream;
						private byte[] buf = new byte[1024];
						private int curChar;
						private int numChars;
						private SpaceCharFilter filter;
						private BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
				 
						public InputReader(InputStream stream)
						{
							this.stream = stream;
						}
						
						public int read()
						{
							if (numChars==-1) 
								throw new InputMismatchException();
							
							if (curChar >= numChars)
							{
								curChar = 0;
								try 
								{
									numChars = stream.read(buf);
								}
								catch (IOException e)
								{
									throw new InputMismatchException();
								}
								
								if(numChars <= 0)				
									return -1;
							}
							return buf[curChar++];
						}
					 
						public String nextLine()
						{
							String str = "";
				            try
				            {
				                str = br.readLine();
				            }
				            catch (IOException e)
				            {
				                e.printStackTrace();
				            }
				            return str;
						}
						public int nextInt()
						{
							int c = read();
							
							while(isSpaceChar(c)) 
								c = read();
							
							int sgn = 1;
							
							if (c == '-') 
							{
								sgn = -1;
								c = read();
							}
							
							int res = 0;
							do 
							{
								if(c<'0'||c>'9') 
									throw new InputMismatchException();
								res *= 10;
								res += c - '0';
								c = read();
							}
							while (!isSpaceChar(c)); 
							
							return res * sgn;
						}
						
						public long nextLong() 
						{
							int c = read();
							while (isSpaceChar(c))
								c = read();
							int sgn = 1;
							if (c == '-') 
							{
								sgn = -1;
								c = read();
							}
							long res = 0;
							
							do 
							{
								if (c < '0' || c > '9')
									throw new InputMismatchException();
								res *= 10;
								res += c - '0';
								c = read();
							}
							while (!isSpaceChar(c));
								return res * sgn;
						}
						
						public double nextDouble() 
						{
							int c = read();
							while (isSpaceChar(c))
								c = read();
							int sgn = 1;
							if (c == '-') 
							{
								sgn = -1;
								c = read();
							}
							double res = 0;
							while (!isSpaceChar(c) && c != '.') 
							{
								if (c == 'e' || c == 'E')
									return res * Math.pow(10, nextInt());
								if (c < '0' || c > '9')
									throw new InputMismatchException();
								res *= 10;
								res += c - '0';
								c = read();
							}
							if (c == '.') 
							{
								c = read();
								double m = 1;
								while (!isSpaceChar(c)) 
								{
									if (c == 'e' || c == 'E')
										return res * Math.pow(10, nextInt());
									if (c < '0' || c > '9')
										throw new InputMismatchException();
									m /= 10;
									res += (c - '0') * m;
									c = read();
								}
							}
							return res * sgn;
						}
						
						public String readString() 
						{
							int c = read();
							while (isSpaceChar(c))
								c = read();
							StringBuilder res = new StringBuilder();
							do 
							{
								res.appendCodePoint(c);
								c = read();
							} 
							while (!isSpaceChar(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;
						}
					 
						public String next() 
						{
							return readString();
						}
						
						public interface SpaceCharFilter 
						{
							public boolean isSpaceChar(int ch);
						}
					}
				 	
					public static void main(String args[]) throws Exception
					{
						new Thread(null, new Solution1(),"Solution1",1<<26).start();
					}
					public static int gcd(int a, int b)
				    {
				        if (a == 0)
				            return b;
				         
				        return gcd(b%a, a);
				    }
					 
					  static int lcm(int a, int b)
					    {
					        return (a*b)/gcd(a, b);
					    }
					static int max=  -1;
					ArrayList<Node> arr[];
					Node[] n1;
					public void run()
					{
						InputReader sc= new InputReader(System.in);
						PrintWriter w= new PrintWriter(System.out);
						int t = sc.nextInt();
						while(t-- > 0){
							int n = sc.nextInt();
							PriorityQueue<Pair> p = new PriorityQueue();
							for(int i = 0;i < n;i++){
								p.add(new Pair(sc.nextInt(),sc.nextInt(),i));
							}
							int current = 0;
							int i = 0;
							int[] ans = new int[n];
							while(!p.isEmpty()){
								Pair z = p.poll();
								if(i == 0){
									ans[z.c] = z.a;
									current = z.a+1;
									i++;
								}
								else{
									if(z.b < current){
										ans[z.c] = 0;
									}else{
										if(z.a < current){
											ans[z.c] = current;
											current++;
										}else{
											ans[z.c] = z.a;
											current = z.a+1;
										}
									}
								}
							}
							for(int j = 0;j < ans.length;j++){
								w.print(ans[j] + " ");
							}
							w.println();
						}
						w.close();
					}
					int count = 0;
					boolean[] visited;
					boolean isCyclicUtil(int v, boolean visited[], boolean[] recStack)
					{
					    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
					        Iterator<Node> it = arr[v].iterator();
					        while(it.hasNext())
					        {
					        	Node x = it.next();
					            if ( !visited[x.a] && isCyclicUtil(x.a, visited, recStack) )
					                return true;
					            else if (recStack[x.a])
					                return true;
					        }
					 
					    }
					    recStack[v] = false;  // remove the vertex from recursion stack
					    return false;
					}
					 
					boolean isCyclic()
					{
					    // Mark all the vertices as not visited and not part of recursion
					    // stack
					    boolean[] visited = new boolean[arr.length];
					    boolean[] recStack = new boolean[arr.length];
					    for(int i = 0; i < arr.length; i++)
					    {
					        visited[i] = false;
					        recStack[i] = false;
					    }
					 
					    // Call the recursive helper function to detect cycle in different
					    // DFS trees
					    for(int i = 0; i < arr.length; i++)
					        if (isCyclicUtil(i, visited, recStack))
					            return true;
					 
					    return false;
					}
					long ans = 0;
					void dfs(int a,int[] freq){
						visited[a] = true;
						freq[n1[a].c-97]++;
						Iterator<Node> it = arr[a].iterator();
						while(it.hasNext()){
							Node f = it.next();
								dfs(f.a,freq);
							
						}
						for(int i = 0;i < 26;i++){
							if(freq[i] > ans){
								ans = freq[i];
							}
						}
						freq[n1[a].c-97]--;
					}
					class Node{
						int a;
						char c;
						Node(int a,char c){
							this.a = a;
							this.c = c;
						}
					}
	static class Pair implements Comparable<Pair>{
							int a;
							int b;	
							int c;
							Pair(int a,int b,int c)	{
								this.a = a;
								this.b = b;
								this.c = c;
							}
							public boolean equals(Object o)
							{
								Pair p = (Pair)o;
								return (p.a==a && p.b==b) || (p.b == a && p.a == b);
							}
							public int compareTo(Pair p){
								if(p.a == this.a){
									return Integer.compare(this.c,p.c);
								}
								return Integer.compare(this.a,p.a);
							}
							public int hashCode()
							{
								return new Long(a).hashCode()*31 + new Long(a).hashCode();
							}
					}
				}