Из общения с Красной королевой Алиса вынесла одну простую мысль — достаточно одного неудачного слова, и тебе отрубят голову. Поэтому Алиса начала шифровать разговоры со своим новым другом Брандашмыгом.

Не так давно ей удалось придумать достаточно простой в применении, но в то же время достаточно надёжный шифр. В качестве ключа Алиса берёт последовательность целых чисел x₁, …, x_n (0 ≤ x_i ≤ a − 1), где a — размер алфавита. Желая передать Брандашмыгу сообщение s = s₁s₂…s_r, она передаёт ему сообщение t = t₁t₂…t_r. При этом номер буквы t₁ в алфавите — это номер буквы s₁ плюс x₁, номер буквы t₂ — это номер буквы s₂ плюс x₂, и так далее (считая, что алфавит циклический, то есть после его последней буквы вновь идёт первая). После того как Алиса произносит первых n букв своего сообщения, она начинает использовать свою последовательность с начала — снова x₁, затем x₂…

Алиса хочет знать, сколько различных ключей существует для её шифра. Алиса считает одинаковыми ключи, отличающиеся только циклическим сдвигом (например, [0, 1, 2, 0] и [2, 0, 0, 1]). Более того, Алиса боится, что её разговор могут подслушать, поэтому она не хочет использовать последовательности с периодом меньше n (которые могут быть представлены в виде более короткой последовательности, повторённой целое число раз, например, [0, 1, 0, 1]).

В единственной строке записаны целые числа a и n (1 ≤ a ≤ 26; 1 ≤ n ≤ 10 000).

Выведите общее количество различных ключей для шифра, который придумала Алиса.