Любимое занятие Луки — наблюдать за кузнечиками. Сегодня утром, прогуливаясь по парку, он обнаружил кузнечика, который прыгал по окружности длиной n метров. Лука заметил, что за один прыжок кузнечик может переместиться по часовой стрелке на k или k+1 метров от своей текущей позиции на окружности. Мальчику стало интересно, какое минимальное количество прыжков потребуется кузнечику, чтобы, начав прыгать из некоторой точки окружности, снова оказаться в ней.

Ввод

Вывод

10

3

3

10

1

5

11

7

3

У Луки есть массив из n целых чисел a1, a2, . . . , an. K каждому элементу массива можно произвольное количество раз применять каждую из следующих магических операций:

Выбрать некоторый элемент массива ai и заменить его на число [ai2] (данная запись обозначает число ai2, округлённое вниз). Для выполнения данной операции требуется k единиц энергии.

Выбрать некоторый элемент массива ai и заменить его на число ai−1. Для выполнения данной операции требуется одна единица энергии.

Ваша задача — определить, какое минимальное количество энергии необходимо, чтобы после выполнения магических операций все элементы массива были равны единице (то есть a1=a2=...=an=1).

Ввод

Вывод

3

1

4

1

3

3

1

100

10

9