D. Не добавлять
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a_1, a_2, \dots, a_n$$$ из $$$n$$$ различных целых чисел. Вы можете выполнять следующую операцию:

  • Выберите два элемента $$$a_i$$$ и $$$a_j$$$ ($$$i \ne j$$$) такие, что $$$\gcd(a_i, a_j)$$$ не встречается среди элементов массива, и добавьте $$$\gcd(a_i, a_j)$$$ в конец массива. Здесь $$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.

Обратите внимание, что после каждой операции массив меняется, и последующие операции выполняются с новым массивом.

Какое максимальное число раз вы можете выполнить операцию?

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^6$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$). Все $$$a_i$$$ различны.

Выходные данные

Выведите одно целое число — максимальное количество операций, которое можно выполнить с данным массивом.

Примеры
Входные данные
5
4 20 1 25 30
Выходные данные
3
Входные данные
3
6 10 15
Выходные данные
4
Примечание

В первом примере один из способов выполнить максимальное число операций такой:

  • Выбрать $$$i = 1, j= 5$$$ и добавить $$$\gcd(a_1, a_5) = \gcd(4, 30) = 2$$$ к массиву.
  • Выбрать $$$i = 2, j= 4$$$ и добавить $$$\gcd(a_2, a_4) = \gcd(20, 25) = 5$$$ к массиву.
  • Выбрать $$$i = 2, j= 5$$$ и добавить $$$\gcd(a_2, a_5) = \gcd(20, 30) = 10$$$ к массиву.

Можно показать, что не существует способа выполнить больше $$$3$$$ операций с массивом.

Во втором примере можно добавить $$$3$$$, затем $$$1$$$, затем $$$5$$$ и $$$2$$$.