На окружности расположено p полей, пронумерованных от 0 до (p - 1) так, что из поля 0 можно перейти в поле 1, из поля 1 в поле 2, и т. д., а из поля (p - 1) можно перейти в поле 0.
Фишка изначально раcположена на поле 0. Она начинает бегать по окружности, делая сперва ход на 1 поле вперед, потом на 2, потом на 3, и т. д.
Сколько уникальных полей (включая начальное) посетит фишка за n ходов?
Входные данные содержат два целых числа p и n (1 ≤ p ≤ 107, 0 ≤ n ≤ 1018) — количество полей на окружности и количество ходов.
Выведите целое число — количество уникальных полей, которое посетит фишка.
3 10
2
5 3
3
8 1000000000000000000
8
