Расписание

시간 제한2초메모리 제한1024 MB

요약

각 칸 (i, j)에 그 행의 앞선 칸들과 그 열의 위쪽 칸들에서 쓰이지 않은 가장 작은 번호를 채울 때, (i, j)의 값을 묻는 질의에 답한다.

난이도: 보통10점 중 5점
유형: 수학, 비트 연산
정답자: 아직 제출이 없습니다

문제

У хозяйки Макса Кэти очень много дел. Для удобства она решила пронумеровать все дела целыми неотрицательными числами в порядке убывания их важности (в частности дело с номером 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$ ).

출력

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

예제2

예제 1
입력
```
6
1 1
2 9
3 2
3 6
5 4
8 8
```
예상 출력
```
0
11
1
5
1
0
```

예제 2

입력

예상 출력