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 l_{i}-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 r_{i}-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 l_{i}, r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ 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 $i \in [ 2 ; n ]$ condition l_{i} - 1 ≤ l_{i} 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:

  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.  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.

Difficulty: interview

Starter code:

Solutions:
t = int(input())

for _ in range(t):
    n = int(input())
    lims = [tuple(int(v) for v in input().split()) for _ in range(n)]
    ctime = 0
    ans = []
    for l, r in lims:
        if l >= ctime:
            ans.append(l)
            ctime = l + 1
        elif r < ctime:
            ans.append(0)
        else:
            ans.append(ctime)
            ctime += 1
    print(' '.join(str(v) for v in ans))


t = int(input())
ans1 = []
for i in range(t):
    n=int(input())
    st=[]
    for i in range(n):
        l,r = map(int,input().split())
        st.append((l,r,i))
    st = sorted(st, key=lambda x: (x[0], x[2]))
    ans = []
    f = -1
    for s in st:
        if s[1] < f:
            ans.append(0)
        else:
            ans.append(max(f, s[0]))
            f = ans[-1]+1
    ans1.append(ans)
for ans2 in ans1:
    print(' '.join([str(i) for i in ans2]))

T = int(input())
for _ in range(T):
    n = int(input())
    studs = [list(map(int,input().split())) for _ in range(n)]
    t = 0
    out = [0]*n
    cs = 0
    while len(studs)>0:
        t += 1
        if studs[0][0]<=t and studs[0][1] >= t:
            out[cs] = t
            cs += 1
            studs.pop(0)
        elif studs[0][0] <= t:
            cs += 1
            studs.pop(0)
            t -= 1
    print(' '.join(map(str,out)))


def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        ss = []
        for i in range(n):
            l, r = [int(x) for x in input().split()]
            ss.append((l, i, r))
        
        ttt = []
        cc = 0
        for t in ss:
            
            if t[0] >= cc:
                ttt.append(t[0])
                cc = t[0] + 1
            elif cc > t[2]:
                ttt.append(0)
            else:
                ttt.append(cc)
                cc += 1
        
        print(' '.join(str(x) for x in ttt))
            
                
        
            

    
def __starting_point():
    main()

__starting_point()

t = int(input())
for i in range(t):
    n = int(input())
    students = []
    for i in range(n):
        students.append(list(map(int, input().split())))    
    time = 0
    ans = []
    for i in students:
        l = i[0]
        r = i[1]
        if r < time:
            ans.append(0)
            continue
        else:
            ans.append(max(time, l))
            time = max(time + 1, l + 1)
    print(*ans)

read = lambda: map(int, input().split())
T = int(input())
for ____ in range(T):
    n = int(input())
    a = []
    for _ in range(n):
        a.append(list(read()))
    t = 0
    while a:
        b = a[0][0]
        if b >= t:
            t = b
            print('%d ' % t, end='')
        else:
            if t > a[0][1]:
                print('0 ', end='')
                del a[0]
                continue
            else:
                print('%d ' % t, end='')
        t += 1
        del a[0]
    print()


t = int(input())
for _ in range(t):
	n = int(input())
	d = []
	for i in range(n):
		d.append(list(map(int, input().split())) + [i])
	d.sort(key = lambda x: x[1])
	d.sort(key = lambda x: x[2])
	d.sort(key = lambda x: x[0])
	res = [[d[0][0], d[0][2]]]
	c = d[0][0]
	i = 0
	while i < len(d):
		while i < len(d) and d[i][1] < c:
			res.append([0, d[i][2]])
			i += 1
		if i < len(d):
			c = max(c + 1, d[i][0] + 1)
			res.append([c - 1, d[i][2]])
		i += 1
	res.pop(0)
	res.sort(key = lambda x: x[1])
	z = [res[i][0] for i in range(len(res))]
	print(*z)


# cook your dish here
# from math import * 
for _ in range(int(input().strip())):
    n=int(input())
    t=1 
    l=[]
    for __ in range(n):
        l.append(list(map(int,input().split())))
    i=0
    ans=[]
    t=1
    while t<=5002:
        if l[i][0]>t:
            t+=1
            continue
        if l[i][0]<=t and l[i][1]>=t:
            ans.append(t)
            t+=1
            i+=1 
        else:
            ans.append(0)
            i+=1
        if i==n:
            break
    print(*ans)        
        


# Put them all in queue in order of l. At popping check: should they be in? (time++)Should they be already out? (0)
t = int(input())
for _ in range(t):
    n = int(input())
    arr = [[int(i) for i in input().split()] + [i] for i in range(n)]
    timearr = [0 for i in range(n)]
    checked = 0
    currtime = 1
    arr.sort(key=lambda a:a[0])
    while checked < n:
        if arr[checked][0] > currtime:
            currtime += 1
        elif arr[checked][1] < currtime:
            checked += 1
        else:
            timearr[arr[checked][2]] = currtime
            currtime += 1
            checked += 1
    print(' '.join(str(i) for i in timearr))






t = int(input())
for y in range(t):
    n = int(input())
    data = []
    tim = 1
    ans = []
    for st in range(n):
        l, r = [int(x) for x in input().split()]
        if(tim <= l):
            tim = l
            ans.append(tim)
            tim +=1
            continue
        if(tim <= r):
            ans.append(tim)
        else:
            ans.append(0)
            continue
        tim+=1

    print(*ans)
    #    data.append([int(x) for x in input().split()])
    



#!/usr/bin/env python3
from sys import stdin, stdout

def rint():
    return list(map(int, stdin.readline().split()))
#lines = stdin.readlines()


t = int(input())

for _ in range(t):
    n = int(input())
    lb, rb = 0, 0
    ct = 0
    ans = []
    for __ in range(n):
        lc, rc = rint()
        if lc >= ct:
            ans.append(lc)
            ct = lc+1
        elif ct <= rc:
            ans.append(ct)
            ct += 1
        else:
            ans.append(0)

    print(*ans)


from collections import deque
def solve(X):

  waiting = deque()
  res = [None]*len(X)
  t = 0
  X.append((10000,10000))
  for i,(l,r) in enumerate(X):
    while waiting and t < l:
      j,b = waiting.popleft()
      if t <= b:
        res[j] = t
        t += 1
      else:
        res[j] = 0 
    waiting.append((i,r))
    t = l

  return res

T = int(input())
for _ in range(T):
  n = int(input())
  X = [tuple(map(int,input().split())) for _ in range(n)]
  res = solve(X)
  print(' '.join(map(str,res)))

def solve(students):
    k = 1
    for s in students:
        if s[1] < k:
            print(0, end=" ")
        else:
            print(max(s[0], k), end=" ")
            if k < s[0]:
                k = s[0] + 1
            else:
                k += 1
    print()


tests = int(input())
while tests:
    tests -= 1
    n = int(input())
    st = []
    for _ in range(n):
        st.append(list(map(int, input().split())))
    solve(st)


for repeat in range(int(input())):
    studentsnum = int(input())
    res = ""
    laststudent = 0
    for i in range(studentsnum):
        inp = input().split(" ", 1)
        arrival = int(inp[0])
        departure = int(inp[1])
        if arrival > laststudent:
            laststudent = arrival
        if departure < laststudent:
            res = res + str(0) + " "
        else:
            res = res + str(laststudent) + " "
            laststudent = laststudent + 1
    print(res)
            


# B

t = int(input())
ans = []

for _ in range(t):
    n = int(input())
    L = []
    R = []
    for _ in range(n):
        l, r = list(map(int, input().split()))
        L.append(l)
        R.append(r)
    time = [0 for _ in range(n)]       # time[j] は人 j の待ち時間
    flag = [0 for _ in range(n)]       # 待ちか否かのフラグ
    for i in range(1, max(R)+1):            # i は時間
        for j in range(n):
            if L[j] == i:
                flag[j] = 1
        for j in range(n):
            if flag[j] == 1:
                flag[j] = 0
                time[j] = i
                break
        for j in range(n):
            if flag[j] == 1 and R[j] == i:
                flag[j] = 0
    ans.append(time)

for i in range(t):
    answer = list(map(str, ans[i]))
    print(" ".join(answer))


import queue
t = int(input())
for i in range(t):
    n = int(input())
    q = queue.Queue()
    answer = []
    current_sec = 1
    for j in range(n):
        s = input().split(" ")
        l = int(s[0])
        r = int(s[1])

        while l > current_sec:
            if not q.empty():
                time = q.get()
                if time >= current_sec:
                    answer.append(str(current_sec))
                    current_sec += 1
                else:
                    answer.append("0")
            else:
                current_sec = l


        if l == current_sec:
            q.put(r)

    while not q.empty():
        time = q.get()
        if time >= current_sec:
            answer.append(str(current_sec))
            current_sec += 1
        else:
            answer.append("0")


    res = " ".join(answer)
    print(res)

t = int(input())

for _ in range(t):
    n = int(input())
    l = [[] for _ in range(5001)]
    r = [[] for _ in range(5001)]
    a = [-1 for _ in range(n)]
    for i in range(n):
        l0, r0 = input().split()
        l[int(l0)].append(i)
        r[int(r0)].append(i)

    q = []
    for e, (l, r) in enumerate(zip(l, r)):
        for h in sorted(l):
            q.insert(0, h)
        if q:
            ch = q.pop()
            a[ch] = e
        for h in r:
            if h in q:
                q.remove(h)
                a[h] = 0

    print(*a)


t = int(input())
bo = []
for i in range(t):
    n = int(input())
    mr = 0
    b = [-2] * n
    l = []
    r = []
    for j in range(n):
        x, y = map(int, input().split())
        if y > mr:
            mr = y
        l.append(x)
        r.append(y)
    j = 1
    k = 0
    h = 0
    while j <= mr:
        if k < n and l[k] == j:
            b[k] = -1
            k += 1
            continue
        for o in range(n):
            if b[o] == -1:
                b[o] = j
                break
        for o in range(n):
            if r[o] == j and b[o] == -1:
                b[o] = 0
        j += 1
    bo.append(b)
for i in range(t):
    print(' '.join(map(str, bo[i])))

# Imports


##############################################
# Input

t = int(input())
##############################################
# Timer start
from time import time
start_time = time()
##############################################
# Main code


for tt in range(t):
    n = int(input())

    stud = []
    for nn in range(n):
        s = tuple(map(lambda x:int(x), input().split()))
        stud.append(s)

    res = 0
    for i in range(n):
        (l, r) = stud[i]
        if i == 0:
            res = l + 1
            print(l, end=" ")
            continue

        newres = max(l, res)
        if newres > r: # go out
            res = newres
            print(0, end=" ")
        else:
            print(newres, end=" ")
            res = newres + 1

    print()







import heapq

def tea_list(students):
    teatimes = [0] * len(students)
    events = []
    for i, (a, l) in enumerate(students):
        events.append((a, 0, (a, i, l)))
    heapq.heapify(events)
    queue_len = 0
    while events:
        t, etype, e = heapq.heappop(events)
        if etype == 0:
            a, i, l = e
            if a + queue_len <= l:
                heapq.heappush(events, (a + queue_len, 1, i))
                queue_len += 1
        elif etype == 1:
            queue_len -= 1
            teatimes[e] = t
    return teatimes

        

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        students = [tuple(int(x) for x in input().split()) for _ in range(N)]
        print(*tea_list(students))

def __starting_point():
    main()

__starting_point()

t = int(input())
for test_index in range(t):
    n = int(input())
    list_of_students = []
    for i in range(n):
        l, r = map(int, input().split())
        list_of_students.append((i, l, r))
    sorted_list = sorted(list_of_students, key = lambda x: (x[1], x[0]), reverse=True)
#    print(sorted_list)
    current_time = 1
    answer = [0 for i in range(n)]
    while (len(sorted_list) > 0):
        current_customer = sorted_list.pop()
        if current_time < current_customer[1]:
            current_time = current_customer[1]
#        print(current_time, current_customer)
        if current_time > current_customer[2]:
            continue
        answer[current_customer[0]] = current_time
        current_time += 1
    for x in answer:
        print(x, end=" ")
    print()


from collections import deque
def solve(ar):
    res = []
    time = 0
    for l, r in ar:
        if r >= time:
            if time == 0:
                time = l + 1
                res.append(l)
            else:
                if l >= time: time = l
                res.append(time)
                time += 1
        else:
            res.append(0)
    return res

t = int(input())
for _ in range(t):
    n = int(input())
    a = []
    for i in range(n):
        a.append(deque(int(x) for x in input().split()))
    print(*solve(a))