Звіт 3

Учасники Міжнародної літньої школи з програмування 2011 року в Севастополі, можливо, пам'ятають, як одного разу фінансист задумався над питанням: чи можливо, маючи від'ємні сумарні показники для кожного інтервалу місяців однакової довжини в певному звітному періоді, все ж отримати додатний сумарний показник за весь період?

Завдяки допомозі учасників школи, які вирішували це питання, стало відомо, що для деяких $N$ можна знайти такі $n$, для яких існує послідовність довжини $N$, сума членів якої додатна, але кожен відрізок довжини $n$ має від'ємну суму. Наприклад, для N=5 можна взяти n=2, а як послідовність обрати $4$, $-5$, $4$, $-5$, $4$. Очевидно, що можна досягти і зворотного ефекту: скласти послідовність довжини $N$, сума членів якої від'ємна, навіть якщо кожен відрізок довжини $n$ має додатну суму. Такі $n$ називаються небезпечними щодо $N$, а всі інші числа називаються безпечними щодо $N$. Нас цікавлять числа, які не перевищують $N$.

У певному Регіоні рівень демократії настільки високий, що кожна організація може самостійно визначити величину свого звітного періоду. Більше того, організації обирають унікальні числа як величину звітного періоду, щоб самоствердитися.

У цьому Регіоні два періоди $N$ і $M$ вважаються конкуруючими, якщо у них є хоча б одне спільне безпечне число, яке більше ніж $1$. Відповідно, організації з конкуруючими величинами звітних періодів також вважаються конкуруючими.

Регіональна служба корпоративного розвитку просить вас створити програму, яка для заданої величини звітного періоду $N$ (1 \le N \le 2 \cdot 10^{10}) певної організації визначить максимально можливу кількість організацій, які не є конкуруючими з даною організацією серед тих, що мають період, який не перевищує $N$, за умови, що період — це ціле число не менше ніж $2$.