A. Увеличить НОД
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Mr. F есть $$$n$$$ положительных целых чисел, $$$a_1, a_2, \ldots, a_n$$$.

Он считает, что наибольший общий делитель этих чисел слишком маленький, и хочет увеличить его, удалив некоторые из чисел.

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

Ваша задача найти минимальное количество чисел, удалив которые, наибольший делитель оставшихся будет строго больше чем наибольший общий делитель всех исходных чисел.

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

В первой строке входного файла записано единственное целое число $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$) — количество чисел у Mr. F.

Во второй строке записаны $$$n$$$ целых чисел, $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 1.5 \cdot 10^7$$$).

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

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

Вы не можете удалить все числа.

Если решения не существует, выведите «-1» (без кавычек).

Примеры
Входные данные
3
1 2 4
Выходные данные
1
Входные данные
4
6 9 15 30
Выходные данные
2
Входные данные
3
1 1 1
Выходные данные
-1
Примечание

В первом примере, НОД изначально $$$1$$$. Вы можете удалить $$$1$$$, НОД увеличится, и станет равным $$$2$$$. Таким образом, ответ $$$1$$$.

Во втором примере, НОД изначально $$$3$$$. Вы можете удалить два числа, $$$6$$$ и $$$9$$$, НОД увеличится, и станет равным $$$15$$$. Можно показать, что удалив одно число, увеличить НОД невозможно. Таким образом, ответ $$$2$$$.

В третьем примере, невозможно удалить числа, чтобы НОД увеличился. Таким образом, ответ $$$-1$$$.