Расписание
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
schedule.in
вывод
schedule.out

У хозяйки Макса Кэти очень много дел. Для удобства она решила пронумеровать все дела целыми неотрицательными числами в порядке убывания их важности (в частности дело с номером 0 самое важное).

Сейчас в распоряжении Кэти находятся n дней, в каждом из которых она выделила m моментов времени (по привычке дни и моменты Кэти также пронумеровала с нуля). Чтобы все успевать и при этом избегать рутины, девушка составила расписание, в котором решила придерживаться следующего правила. В i-ый день в момент времени j Кэти выбирает самое важное (минимальное по номеру) дело такое, которое она не делала в этот день ранее (то есть в моменты от 0 до j - 1) и в прежние дни в j-ые моменты времени (в частности в нулевой день в нулевой момент Кэти будет занята делом 0).

Очень скоро Кэти поняла, что дела в таком расписании будут распределены единственным образом, а значит она сможет с легкостью узнавать, что ей необходимо сделать в каждый конкретный момент времени. Помогите ей в этом.

Входные данные

В первой строке входного файла заданo одно натуральное число k — количество запросов (1 ≤ k ≤ 105).

В следующих k строках следуют сами запросы, каждый запрос — пара целых неотрицательных чисел (i, j), где i — номер дня и j — номер момента (0 ≤ i, j ≤ 109).

Выходные данные

Для каждого запроса в отдельной строке выведите одно число — номер дела, которое необходимо выполнить в заданный момент времени.

Примеры

Входные данные
6
1 1
2 9
3 2
3 6
5 4
8 8
Выходные данные
0
11
1
5
1
0
Входные данные
4
25 36
59 78
87 103
100 243
Выходные данные
61
117
48
151