분류 모자

마법 학교는 오래전부터 마법 모자로 학생을 각 학부에 배정한다. 예전에는 학부가 4개였지만, 학교를 개편한 뒤 학부 수가 $p$개로 바뀌었다. 모자는 지금도 학생 배정에 쓰인다.

배정 계획은 수열 $a[1], a[2], \dots, a[k]$로 나타낸다. $a[i]$는 $i$번 학생이 들어갈 학부다.

모자가 계획을 만드는 방법은 다음과 같다. 학부에는 $0$부터 $p-1$까지 번호가 붙어 있다. $x$ 다음 학부를 $\text{next}(x)$라 하면, $x < p-1$일 때 $\text{next}(x) = x+1$이고 $\text{next}(p-1) = 0$이다. 계획은 원소가 $0$ 하나뿐인 수열에서 시작한다. 한 단계를 거칠 때마다 원소가 $k$개인 수열 $a$는 원소가 $2k$개인 새 수열 $a[1], a[2], \dots, a[k], \text{next}(a[1]), \text{next}(a[2]), \dots, \text{next}(a[k])$가 된다.

학부가 4개일 때 학생 9명을 배정하는 과정을 보자. 모자는 다음 순서로 계획을 늘린다.

$(0) \to (0, 1) \to (0, 1, 1, 2) \to (0, 1, 1, 2, 1, 2, 2, 3) \to (0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 0)$

마지막 수열의 길이는 학생 9명을 배정하기에 충분하다. 단계를 계속 반복하면 수열은 얼마든지 길어지므로, 어떤 학생 번호든 배정 학부가 정해진다.

$n$과 $p$가 여러 쌍 주어진다. 학부가 $p$개일 때 $n$번 학생이 어느 학부에 들어가는지 구하여라. 학생 번호는 1번부터 시작한다.

첫째 줄에 질의의 개수 $Q$가 주어진다 ($1 \le Q \le 310\,000$).

다음 $Q$개의 줄에 각각 두 정수 $n$과 $p$가 이 순서대로 공백으로 구분되어 주어진다 ($1 \le n \le 10^{18}$, $2 \le p \le 10^{18}$).

$Q$개의 줄에 각 질의의 답을 입력 순서대로 출력한다. 각 줄에는 $n$번 학생이 들어갈 학부의 번호를 출력한다.