Мы говорим, что натуральное число \(n\) является \(k\)-хорошим для некоторого положительного целого числа \(k\), если \(n\) можно представить в виде суммы \(k\) целых положительных чисел, которые дают \(k\) различных остатков при делении на \(k\).
По заданному натуральному числу \(n\) найдите такое \(k \geq 2\), что \(n\) является \(k\)-хорошим, или скажите, что такого \(k\) не существует.
Выходные данные
Для каждого набора входных данных выведите строку со значением \(k\) таким, что \(n\) является \(k\)-хорошим (\(k \geq 2\)), или \(-1\), если \(n\) не является \(k\)-хорошим для любых \(k\). Если существует несколько допустимых значений \(k\), вы можете вывести любое из них.
Примечание
\(6\) является \(3\)-хорошим числом, поскольку его можно представить в виде суммы \(3\) чисел, которые дают разные остатки при делении на \(3\): \(6 = 1 + 2 + 3\).
\(15\) также является \(3\)-хорошим числом, поскольку \(15 = 1 + 5 + 9\), а \(1, 5, 9\) дают разные остатки при делении на \(3\).
\(20\) — это \(5\)-хорошее число, поскольку \(20 = 2 + 3 + 4 + 5 + 6\) и \(2,3,4,5,6\) дают разные остатки при делении на \(5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
4
6
15
20
|
-1
-1
3
3
5
|