Недавно студенты из города С. поехали на сборы в город П. Всего на сборы отправилось n студентов.
Вечером в поезде возникла очередь за чаем. Студент с номером i приходит в очередь к чайнику в начале секунды li. Студенты приходят в очередь в порядке увеличения их номеров (то есть если два студента придут в очередь в одно и то же время, первым будет тот, у кого меньше номер). Если очередь пуста — он за одну секунду наливает себе чай и уходит. Иначе же он ждёт, пока все студенты перед ним нальют себе чай и уйдут. Если в начале секунды ri i-й студент до сих пор не может налить себе чай (кто-то до сих пор перед ним в очереди), он просто уходит из очереди.
Помогите определить для каждого студента, в какой момент времени он нальёт себе чай, или же определите, что он не дождётся этого момента и покинет очередь.
В первой строке входных данных задано одно число t (1 ≤ t ≤ 1000) — количество наборов тестовых данных, для которых нужно решить задачу.
Затем следуют t наборов. Первая строка набора содержит единственное целое число n (1 ≤ n ≤ 1000) — количество студентов.
В следующих n строках набора задано по два целых числа li, ri (1 ≤ li ≤ ri ≤ 5000) — момент времени, в который студент с номером i приходит в очередь, и момент времени, после которого студент уйдёт, если не успеет налить себе чай.
Гарантируется, что для любого 
выполняется li - 1 ≤ li.
Гарантируется, что сумма n по всем наборам не превосходит 1000.
Обратите внимание, во взломах можно использовать только t = 1.
Для каждого набора выведите n чисел. i-е число — момент времени, в который студент i нальёт себе чай, или же 0, если студент не сможет этого сделать.
2
2
1 3
1 4
3
1 5
1 1
2 3
1 2
1 0 2
Пример содержит 2 набора:
- В 1-ю секунду студенты 1 и 2 встают в очередь, и студент 1 наливает себе чай. Студент 2 наливает себе чай во 2-ю секунду.
- В 1-ю секунду студенты 1 и 2 встают в очередь, студент 1 наливает себе чай, и студент 2 уходит без чая. Во 2-ю секунду приходит студент 3 и наливает себе чай.
