Вам дан массив \(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\).
Обратите внимание, что после каждой операции массив меняется, и последующие операции выполняются с новым массивом.
Какое максимальное число раз вы можете выполнить операцию?
Выходные данные
Выведите одно целое число — максимальное количество операций, которое можно выполнить с данным массивом.
Примечание
В первом примере один из способов выполнить максимальное число операций такой:
- Выбрать \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 20 1 25 30
|
3
|
|
2
|
3
6 10 15
|
4
|