//
below I use divisibility by a real (not integer) number - hope that doesn't cause any confusions
//

Let us denote beta = Pi - alpha (from problem statement)

You can easily prove that the process described in the problem statement means that we simply fix the initial point on a circle, and then jump around with angle beta.

So now for given N you need to find the number of solutions for the following equalty:

N * beta mod 2Pi = 0, such that N is minimal

Obviously, beta must be p / N * Pi, where p is integer (elseway N * beta can't be divisible by 2Pi).

But beta = Pi - alpha and 0 < alpha < Pi, so 0 < beta < Pi;
this means that 0 <= p < N. On the other hand, p must be even - if it's not, N * beta = N * p / N * Pi = p * Pi will not be divisible by 2Pi. So p = 2 * i.

So we have the following candidates for beta: 2 * i / N * Pi, where 0 <= i < N div 2 (because p < N).

The last thing to take care of is that there's no such K < N that K * beta is divisible by 2Pi:

K * 2 * i / N * Pi (not divisble by) 2Pi.

This means that K * i must not be divisible by N for any K < N; which means that i and N must be coprimes.

So the answer is number of coprimes of N that are smaller that N / 2. If A and N are coprimes, then (N-A) and N are coprimes too, so the answer is (number of coprimes of N that are smaller that N) / 2.

To calculate this number we can use Euler's formula instead of a bruteforce solution:

if N = a1^p1 * a2^p2 * .. * ak^pk, where all ai are different and all ai are primes, then number of coprimes smaller than N is

E(N) = (a1 - 1) * .. * (ak - 1)   *   a1 ^ (p1 - 1) * .. * ak ^ (pk - 1)

so the answer is E(N) / 2

Thank you! I have got AC....