У Mr. F есть \(n\) положительных целых чисел, \(a_1, a_2, \ldots, a_n\).
Он считает, что наибольший общий делитель этих чисел слишком маленький, и хочет увеличить его, удалив некоторые из чисел.
Но эта задача показалась ему слишком простой, поэтому он не хочет решать ее сам. Если вы ему поможете, он даст вам несколько баллов в качестве вознаграждения.
Ваша задача найти минимальное количество чисел, удалив которые, наибольший делитель оставшихся будет строго больше чем наибольший общий делитель всех исходных чисел.
Выходные данные
Выведите одно целое положительное число — минимальное количество чисел, удалив которые, наибольший делитель оставшихся будет строго больше чем наибольший общий делитель всех исходных чисел.
Вы не можете удалить все числа.
Если решения не существует, выведите «-1» (без кавычек).
Примечание
В первом примере, НОД изначально \(1\). Вы можете удалить \(1\), НОД увеличится, и станет равным \(2\). Таким образом, ответ \(1\).
Во втором примере, НОД изначально \(3\). Вы можете удалить два числа, \(6\) и \(9\), НОД увеличится, и станет равным \(15\). Можно показать, что удалив одно число, увеличить НОД невозможно. Таким образом, ответ \(2\).
В третьем примере, невозможно удалить числа, чтобы НОД увеличился. Таким образом, ответ \(-1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 4
|
1
|
|
2
|
4
6 9 15 30
|
2
|
|
3
|
3
1 1 1
|
-1
|