일정표

맥스의 주인인 캐티는 해야 할 일이 아주 많다. 편의를 위해 그녀는 모든 일에 0 이상의 정수 번호를 붙였다. 번호가 작을수록 중요하며, 0번 일이 가장 중요하다.

캐티에게는 $n$일이 있고, 각 날마다 $m$개의 시각이 있다. 날짜와 시각도 0부터 번호를 매긴다. 캐티는 다음 규칙에 따라 일정을 짰다.

$i$일 $j$시각에 캐티는 다음 두 조건을 모두 만족하는 일 중 번호가 가장 작은 일을 한다. 같은 날 0시각부터 $j-1$시각까지 하지 않은 일이어야 하고, 이전 날들의 $j$시각에 하지 않은 일이어야 한다. 0일 0시각에는 0번 일을 한다.

이 규칙에 따라 각 일이 단 하나로 정해진다. 캐티는 각 시각에 무엇을 해야 하는지 바로 알고 싶어 한다. 이를 대신 구하는 프로그램을 작성하라.

첫 줄에 자연수 $k$가 주어진다. 이는 질의의 개수이다($1 \le k \le 10^5$). 이어지는 $k$개의 줄에는 각각 질의 $(i, j)$가 주어진다. $i$는 날짜 번호, $j$는 시각 번호이다($0 \le i, j \le 10^9$).

각 질의마다 한 줄에 그 날짜와 시각에 캐티가 해야 할 일의 번호를 출력한다.