Конкуренція

Учасники Міжнародної літньої школи з програмування в Севастополі (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 \leq N \leq 2 \cdot 10^{10}) для певної організації визначає, яку максимальну кількість організацій, що не конкурують із заданою, можна вибрати серед тих, чий період не перевищує $N$, за умови, що період — це ціле число не менше $2$.