해리 포터와 분류 모자

아주 오래전부터 학생들을 기숙사로 나누는 일은 마법 모자가 맡아 왔다. 예전에는 학교에 기숙사가 네 개 있었지만, 최근 개혁으로 기숙사가 $p$개가 되었다. 그래도 모자는 여전히 학생들을 나눈다.

축제 전에 모자는 학생들을 기숙사에 배정하는 계획을 미리 세운다. 계획은 수열 $a_1, a_2, \ldots, a_k$이며, 여기서 $a_i$는 $i$번째 학생이 배정될 기숙사 번호이다.

모자는 기숙사 번호로 0부터 $p-1$까지를 사용한다. $i$번 기숙사의 다음은 $(i+1)$번 기숙사이고, $(p-1)$번 기숙사의 다음은 0번 기숙사이다. 처음 계획은 0번 기숙사 하나뿐이다. 그 뒤 모자는 현재 계획을 끝에 계속 덧붙이되, 각 기숙사를 그다음 기숙사로 바꾼다.

기숙사 네 개에 학생 아홉 명을 배정하는 경우를 보자. 모자가 만드는 계획은 차례로 $(0)$, $(0, 1)$, $(0, 1, 1, 2)$, $(0, 1, 1, 2, 1, 2, 2, 3)$, $(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 0)$이다. 마지막 계획의 길이가 모든 학생을 배정하기에 충분하므로, 그 뒤의 계획은 만들지 않는다.

$n$번째 학생이 $p$개의 기숙사 중 어느 기숙사에 배정되는지 구하라.

첫 줄에 질의의 수 $q$ ($1 \le q \le 100{,}000$)가 주어진다. 다음 $q$개의 줄에는 각각 두 정수 $n$과 $p$ ($1 \le n \le 10^{18}$, $2 \le p \le 10^{18}$)가 주어진다. $n$은 학생 번호이고, $p$는 기숙사의 수이다.

각 질의에 대해 $n$번째 학생이 배정되는 기숙사 번호를 한 줄에 하나씩 출력한다.