Тяночку бы

Сложность: 7%

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

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

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

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

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

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

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

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

Подзадачи

баллынеобх. подзадачиограничения
1

1

-

n105n \le 10^5

2

1

-

nn - простое число

3

98

1, 2

Нет дополнительных ограничений

STDINSTDOUT
31
0