Harry Potter and the Sorting Hat

Since ancient times, a magic hat has sorted students into houses. Earlier the school had four houses, but after recent reforms there are $p$ of them. The hat still does the sorting.

Before the ceremony, the hat prepares a plan in advance. The plan is a sequence $a_1, a_2, \ldots, a_k$, where $a_i$ is the number of the house that the $i$-th student goes to.

The hat numbers the houses from $0$ to $p-1$. The house after house $i$ is house $(i+1)$, and the house after house $(p-1)$ is house $0$. The first version of the plan contains only house $0$. After that, the hat repeatedly appends the current plan to its own end, replacing each house with the next one.

Consider sorting nine students into four houses. The hat builds these plans in order: $(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)$. The length of the last plan is enough for all students, so the hat does not build any further plans.

For the $n$-th student, find the house among the $p$ houses that the hat assigns.

The first line contains the number of queries $q$ ($1 \le q \le 100{,}000$). Each of the next $q$ lines contains two integers $n$ and $p$ ($1 \le n \le 10^{18}$, $2 \le p \le 10^{18}$), where $n$ is the student number and $p$ is the number of houses.

For each query, print the house number assigned to the $n$-th student on its own line.