Competition

Participants of the International Summer School on Programming in Sevastopol (2011) are familiar with a question once posed by a financier: Is it possible, having negative cumulative indicators for each interval of months of the same length within a certain reporting period, to still achieve a positive cumulative result for the entire reporting period?

With the help of the school participants, it was discovered that for some $N$, there exists $n$ such that a sequence of length $N$ can be found where the total sum is positive, yet every segment of length $n$ sums to a negative number. For example, for N = 5, n = 2, the sequence 4, -5, 4, -5, 4 exhibits this property. Conversely, a similar effect can be achieved in reverse: constructing a sequence of length $N$ where the sum is negative, although every segment of length $n$ sums to a positive number. Such $n$ is called dangerous with respect to $N$, and all other numbers are considered safe with respect to $N$. We are interested in numbers not exceeding $N$.

In a certain Region, the level of democracy is so high that every organization can independently determine the size of its reporting period. Moreover, it is known that, in an effort to assert themselves, organizations always choose unique numbers for their reporting period sizes.

In this Region, two periods $N$ and $M$ are considered competing if they share at least one common safe number greater than $1$. Accordingly, organizations with competing reporting period sizes are also considered competing.

The Regional Corporate Development Service asks you to write a program that, given the reporting period size $N$ (1 \leq N \leq 2 \cdot 10^{10}) for a certain organization, determines the maximum possible number of organizations that do not compete with the given organization, choosing from those with a period not exceeding $N$, under the condition that the period is an integer not less than $2$.