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 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.
[samples]
## 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.
最近，来自城市 S 的 #cf_span[n] 名学生前往城市 P 参加编程训练营。
他们乘坐火车前往。晚上，火车上的所有学生都想喝茶。当然，不能有两个人同时使用同一个茶壶，因此学生们需要排队取茶。
第 #cf_span[i] 名学生在第 #cf_span[li] 秒开始时到达队列末尾。如果在同一时刻有多个学生到达队列，则索引较大的学生排在索引较小的学生之后。队列中的学生行为如下：如果该学生前面没有人，则他使用茶壶恰好一秒，然后带着茶离开队列；否则，他需要等待前面的人取完茶。如果在第 #cf_span[ri] 秒开始时，第 #cf_span[i] 名学生仍然无法取到茶（队列中仍有他前面的人），则他离开队列而没有得到茶。
请为每个学生确定他使用茶壶并得到茶的时刻（如果他确实得到了茶）。
第一行包含一个整数 #cf_span[t] —— 需要解决的测试用例数量（#cf_span[1 ≤ t ≤ 1000]）。
接下来是 #cf_span[t] 个测试用例。每个测试用例的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1000]）—— 学生人数。
接下来是 #cf_span[n] 行，每行包含两个整数 #cf_span[li], #cf_span[ri]（#cf_span[1 ≤ li ≤ ri ≤ 5000]）—— 第 #cf_span[i] 名学生到达队列末尾的时刻，以及如果他仍未得到茶则离开队列的时刻。
保证对于每个 i 满足条件 #cf_span[li - 1 ≤ li]。
所有测试用例中 #cf_span[n] 的总和不超过 #cf_span[1000]。
*注意：在 Hack 中必须设置 #cf_span[t = 1]*。
对于每个测试用例，输出 #cf_span[n] 个整数。第 #cf_span[i] 个整数应等于第 #cf_span[i] 名学生得到茶的时刻，如果他未得到茶则输出 #cf_span[0]。
## Input
第一行包含一个整数 #cf_span[t] —— 需要解决的测试用例数量（#cf_span[1 ≤ t ≤ 1000]）。接下来是 #cf_span[t] 个测试用例。每个测试用例的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 1000]）—— 学生人数。接下来是 #cf_span[n] 行，每行包含两个整数 #cf_span[li], #cf_span[ri]（#cf_span[1 ≤ li ≤ ri ≤ 5000]）—— 第 #cf_span[i] 名学生到达队列末尾的时刻，以及如果他仍未得到茶则离开队列的时刻。保证对于每个 i 满足条件 #cf_span[li - 1 ≤ li]。所有测试用例中 #cf_span[n] 的总和不超过 #cf_span[1000]。*注意：在 Hack 中必须设置 #cf_span[t = 1]*。
## Output
对于每个测试用例，输出 #cf_span[n] 个整数。第 #cf_span[i] 个整数应等于第 #cf_span[i] 名学生得到茶的时刻，如果他未得到茶则输出 #cf_span[0]。
[samples]
## Note
示例包含 #cf_span[2] 个测试用例：在第 #cf_span[1] 秒，学生 #cf_span[1] 和 #cf_span[2] 到达队列，学生 #cf_span[1] 得到茶。学生 #cf_span[2] 在第 #cf_span[2] 秒得到茶。在第 #cf_span[1] 秒，学生 #cf_span[1] 和 #cf_span[2] 到达队列，学生 #cf_span[1] 得到茶，学生 #cf_span[2] 未得到茶而离开。在第 #cf_span[2] 秒，学生 #cf_span[3] 到达并得到茶。
**Definitions**
Let $ t \in \mathbb{Z} $ be the number of test cases.
Let $ T = \{(n_k, S_k) \mid k \in \{1, \dots, t\}\} $ be the set of test cases, where for each $ k $:
- $ n_k \in \mathbb{Z} $ denotes the number of students.
- $ S_k = \{(l_i, r_i) \mid i \in \{1, \dots, n_k\}\} $ is a sequence of student arrival and departure constraints, with $ l_i \leq r_i $, and $ l_{i-1} \leq l_i $ for $ i > 1 $.
**Constraints**
1. $ 1 \leq t \leq 1000 $
2. For each test case $ k $:
- $ 1 \leq n_k \leq 1000 $
- $ 1 \leq l_i \leq r_i \leq 5000 $ for all $ i \in \{1, \dots, n_k\} $
- $ l_{i-1} \leq l_i $ for $ i \in \{2, \dots, n_k\} $
3. $ \sum_{k=1}^{t} n_k \leq 1000 $
**Objective**
For each test case $ k $, compute an array $ A_k = (a_1, a_2, \dots, a_{n_k}) $, where $ a_i \in \mathbb{Z}_{\geq 0} $ is:
- The second at which student $ i $ begins using the teapot (i.e., the integer time $ t \in [l_i, r_i] $ when the teapot becomes available and $ t \leq r_i $),
- Or $ 0 $ if student $ i $ leaves without tea (i.e., no $ t \in [l_i, r_i] $ exists such that the teapot is free at time $ t $ and all prior students have finished).
The teapot is used by exactly one student at a time, for exactly one second. Students arrive at time $ l_i $ and join the queue in order of increasing index if $ l_i $ are equal. The next student in queue begins using the teapot at the earliest time $ \geq \max(\text{previous finish time}, l_i) $, provided this time $ \leq r_i $.