| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 21 | 14 | 11 | 61.111% |
Испокон веков разделением учеников на факультеты занимается волшебная шляпа. Раньше в школе было четыре различных факультета, но после недавних реформ факультетов стало $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$-го ученика.
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