\begin{problem}{Гарри Поттер и Распределяющая Шляпа}{hat.in}{hat.out}{2 секунды}{256 мегабайт}

%Автор задачи: Демид Кучеренко
%Автор условия: Андрей Комаров

Испокон веков разделением учеников на факультеты занимается волшебная шляпа. 
Раньше в школе было четыре различных факультета, но после недавних реформ 
факультетов стало $p$. Шляпа же всё ещё занимается распределением учеников. 

Перед торжественной церемонией шляпа заранее составляет план распределения учеников по факультетам. 
План является последовательностью чисел $a_1, a_2, \ldots, a_k$, где $a_i$ является номером факультета, 
на который попадет $i$-й ученик.

В своём плане шляпа использует для факультетов номера от $0$ до $p-1$. Следующим за $i$-м факультетом считается
$(i+1)$-й, за $(p-1)$-м~--- нулевой. Первая версия плана содержит только один факультет~--- нулевой.
После чего шляпа много раз дописывает в конец плана текущее содержимое плана, заменив каждый факультет на следующий.

Рассмотрим распределение девяти учеников по четырём факультетам.
Шляпа будет последовательно строить следующие планы: $(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)$.
Длина последнего плана достаточна для распределения всех учеников по факультетам, поэтому следующие планы шляпа может не строить. 
% //шляпа такая шляпа 

Скажите, на какой из $p$ факультетов шляпа распределит $n$-го ученика.

\InputFile
В первой строке задано число $q$ ($1 \le q \le 100{\,}000$)~--- количество запросов. 
В следующих $q$ строках описаны запросы.
Каждый запрос содержит два целых числа $n$ и $p$ ($1 \le n \le 10^{18}$, $2 \le p \le 10^{18}$)~--- 
номер ученика и количество факультетов в Хогвартсе.

\OutputFile
Для каждого запроса выведите одно число~--- номер факультета, на который шляпа распределит $n$-го ученика.

\Example
\begin{example}%
\exmp{
10
1 4
2 4
3 4
4 4
5 4
6 4
7 4
8 4
9 4
10 4
}{
0
1
1
2
1
2
2
3
1
2
}%
\end{example}

\Note

Решения, работающие для $n \le 1000$, $q \le 1000$, $p \le 1000$, будут набирать 30 баллов.

Решения, работающие для $n \le 10{\,}000{\,}000$, будут набирать 60 баллов.
\end{problem}
