Всем известно, что победа в Sort Me Round гарантирует успех в личной жизни. К сожалению, прошлый раунд был нерейтинговым, поэтому Гена в ожидании следующего раунда решил пойти знакомиться с девушками своими силами.

Главная проблема Гены - неуверенность в себе. Каждый раз перед тем, как подойти к потенциальной пассии, ему кажется, что его шансы на успех равны нулю. Чтобы переубедить себя в этом, он решил найти научный способ посчитать вероятность, что конкретная девочка обратит на него внимание.

Гене показалась правдивой формула, которую в прошлом веке предложил испанский психолог Чил Падро. Она гласит, что если $n$ - это кокетливость девушки, $m$ - самоуверенность Гены, а $\gcd{}$ - функция нахождения наибольшего общего делителя, то шанс на то, что девушка обратит внимание на Гену, равен $(\gcd{(n, n + 1)} - 1) \cdot m$.

Безошибочно вычислить кокетливость девушки Гене под силу, а вот объективно оценить свою самоувереность - нет. Ваша задача - по заданному $n$ вычислить максимально возможный шанс, что девушка с кокетливостью $n$ заинтересуется Геной.

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

В первой строке находится одно число $n$ ($1 \le n \le 10^{18}$) - кокетливость девочки.

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

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

Подзадачи