Вам дано натуральное число \(k\). Найдите наибольшее натуральное число \(x\), где \(1 \le x < k\), такое, что \(x! + (x - 1)!^\dagger\) кратно \(^\ddagger\) числу \(k\), или определите, что такого \(x\) не существует.
\(^\dagger\) \(y!\) обозначает факториал числа \(y\): \(0! = 1\), а для \(y \geq 1\) факториал задаётся рекуррентно: \(y! = y \cdot (y-1)!\). Например, \(5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0! = 120\).
\(^\ddagger\) Если \(a\) и \(b\) — целые числа, то \(a\) кратно \(b\), если существует целое число \(c\) такое, что \(a = b \cdot c\). Например, \(10\) кратно \(5\), но \(9\) не кратно \(6\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — наибольшее возможное натуральное число \(x\), удовлетворяющее условиям выше.
Если такого \(x\) не существует, выведите \(-1\).
Примечание
В первом наборе \(2! + 1! = 2 + 1 = 3\), что кратно \(3\).
В третьем наборе \(7! + 6! = 5040 + 720 = 5760\), что кратно \(8\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
6
8
10
|
2
5
7
9
|