The Sorting Hat

A school of magic has always sorted its students into departments with an enchanted hat. The school used to have 4 departments, but after a reorganization it has $p$ of them. The hat still does the sorting.

A sorting plan is a sequence $a[1], a[2], \dots, a[k]$, where $a[i]$ is the department that student $i$ joins.

The hat builds a plan like this. The departments are numbered from $0$ to $p-1$. Write $\text{next}(x)$ for the department after $x$, so $\text{next}(x) = x+1$ when $x < p-1$ and $\text{next}(p-1) = 0$. The plan starts as a sequence with the single element $0$. After each step, a sequence $a$ with $k$ elements becomes the sequence $a[1], a[2], \dots, a[k], \text{next}(a[1]), \text{next}(a[2]), \dots, \text{next}(a[k])$ with $2k$ elements.

Here is how 9 students are sorted into 4 departments. The hat grows the plan in this order:

$(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)$

The last sequence is long enough for 9 students. Repeating the step makes the sequence as long as you like, so every student number gets a department.

You are given several pairs $n$ and $p$. For each pair, report the department that student $n$ joins when the school has $p$ departments. Students are numbered from 1.

The first line contains the number of queries $Q$ ($1 \le Q \le 310\,000$).

Each of the next $Q$ lines contains two integers $n$ and $p$ in that order, separated by a space ($1 \le n \le 10^{18}$, $2 \le p \le 10^{18}$).

Print $Q$ lines, one answer per query, in the order the queries are given. Each line holds the number of the department that student $n$ joins.