Испокон веков разделением задач на спринты занимаются на планировании. На каждом планировании менеджер распределяет задачи на следующие p спринтов.

Перед торжественной церемонией презентация результатов планирования менеджер составляет план распределения задач по спринтам. План является последовательностью чисел a₁, a₂, ... , 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 ≤ q ≤ 100 000) - количество запросов. В следующих q строках описаны запросы. Каждый запрос содержит два целых числа n и p (1 ≤ n ≤ 10¹⁸, 2 ≤ p ≤ 10¹⁸) - номер задачи и количество спринтов планирования.

Формат выходных данных

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

Пример