Считалка у костра
Вечером у костра на берегу Сон-Куля n детей встали в круг и пронумеровались по часовой стрелке от 1 до n. Вожатый Улан начинает считалку с ребёнка номер 1: считает по кругу детей, оставшихся в игре, и k-й по счёту выбывает. Следующий отсчёт начинается с ребёнка, стоящего за выбывшим. Последний оставшийся ребёнок получает приз — горячий боорсок.
Для каждой из T игр найдите номер победителя.
Входные данные
В первой строке — число T (1 ≤ T ≤ 20). В каждой из следующих T строк — два целых числа n и k (1 ≤ n ≤ 10¹⁸, 1 ≤ k ≤ 10⁴).
Выходные данные
Для каждой игры выведите номер победителя.
Пример 1
Вход:
3
7 3
10 2
1 10000
Выход:
4
5
1
Пояснение
При n = 7, k = 3 дети выбывают в порядке 3, 6, 2, 7, 5, 1 — побеждает ребёнок номер 4.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 15 % тестов n ≤ 2000, ещё в 5 % тестов n ≤ 10⁶.
Подсказка
Задача Иосифа Флавия. При n ≥ k за один круг выбывают сразу ⌊n / k⌋ детей.
Комментарии