Вы думаете, что магия — простая штука? Помахал себе руками, пробубнил непонятные слова — и всё готово, вокруг расцветают дивные сады, а во врага несется сметающий всё на своём пути файрболл.

На самом деле всё куда сложнее. Чтобы достичь мастерства, юные волшебники годами изучают такие дисциплины, как магический анализ и прикладная демонология.

Например, прямо сейчас Олег, студент института магии и колдовских наук (ИМКН), готовится к экзамену. И у него ну никак не получается взять определитель Дамблдора. Как вы, наверное, уже догадались, Олег попросил помощи именно у вас.

На случай, если вы прогуливали пары по теории нелинейных заклинаний, кратко напомним вам основные определения. По теореме Гэндальфа, любая часть подпространства может быть представлена в виде вектора магических потенциалов — попросту говоря, массива из n целых положительных чисел. Определитель Дамблдора от этого массива равен минимальному количеству элементарных магических преобразований, необходимых для превращения исходного массива в массив, в котором все элементы равны единице. Одно элементарное магическое преобразование превращает исходный массив длины k в новый массив длины k · (k − 1) / 2, при этом элементами нового массива являются наибольшие общие делители каждой пары элементов исходного массива. Например, массив {2, 3, 3, 6} после применения элементарного магического преобразования превращается в массив {НОД(2, 3), НОД(2, 3), НОД(2, 6), НОД(3, 3), НОД(3, 6), НОД(3, 6)}, то есть в {1, 1, 2, 3, 3, 3}.

В первой строке дано число n — количество чисел в исходном массиве (3 ≤ n ≤ 10 000). В следующих n строках записаны элементы массива — целые положительные числа, не превосходящие 10⁷.

В единственной строке выведите значение определителя Дамблдора для исходного массива. Если определитель не определён или превосходит 10¹⁸, выведите «infinity».