Гарри Поттер и Распределяющая Шляпа

Испокон веков разделением учеников на факультеты занимается волшебная шляпа. Раньше в школе было четыре различных факультета, но после недавних реформ факультетов стало $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$-го ученика.

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

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