Расписание

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

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

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

В первой строке входного файла заданo одно натуральное число $k$ --- количество запросов ($1 \le k \le 10^5$).

В следующих $k$ строках следуют сами запросы, каждый запрос --- пара целых неотрицательных чисел $(i, j)$, где $i$ --- номер дня и $j$ --- номер момента ($0 \le i, j \le 10^9$).

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