Хай живе намисто#7079

Хай живе намисто

1 секунда

64 мегабайти

Середня

Компанія "Хай живе намисто" знаходиться зверху у Консервному ряді $700$ у Монтереї, Каліфорнія. З назви можна зрозуміти, що її бізнесом є намистинки. PR відділ з'ясував, що більше усього клієнти зацікавлені у придбанні кольорових браслетів. Проте більше $90$ процентів цільової аудиторії наполягає на тому, щоб браслети були унікальними (ви лише уявіть собі, що станеться, якщо дві жінки покажуть однакові браслети на спільній вечірці!). Гарна новина полягає у тому, що браслети можуть мати різну довжину, і не обов'язково складатися з намистинок однакового кольору. Допоможіть босу обчислити максимальний прибуток, оцінивши кількість різних браслетів, які його компанія може виготовити.

Браслет являє собою циклічну послідовність з $n$ намистинок, кожна з яких має один з $k$ різних кольорів. Браслет є замкнутим, тобто не має ні початку, ні кінця. Браслет також не має напрямку. Вважайте, що у вас є необмежена кількість намистинок кожного кольору. Для різних значень $n$ та $k$ потрібно підрахувати кількість різних браслетів, які можна виготовити.

Вхідні дані

Кожен рядок є окремим тестом і містить два числа: кількість можливих кольорів $k$ та довжину браслетів $n$ . Останній рядок містить $k = 0$ k = 0 та $n = 0$ n = 0 і не опрацьовується. Обидва числа додатні, і через технічні труднощі з виготовленням браслетів $k \cdot n \leq 32$ k \cdot n \le 32, тобто їхній добуток не перевищує $32$ .

Вихідні дані

Для кожного тесту виведіть в окремому рядку кількість різних браслетів. На рисунку знизу зображено $8$ різних браслетів, виготовлених з $2$ кольорів та $5$ намистинок.

Приклади

Приклад 1