This problem is a programming version of Problem 64 from projecteuler.net
All square roots are periodic when written as continued fractions and can be written in the form:
For example, let us consider :
If we continue we would get the following expansion:
The process can be summarised as follows:
It can be seen that the sequence is repeating. For conciseness, we use the notation , to indicate that the block repeats indefinitely.
The first ten continued fraction representations of (irrational) square roots are:
Exactly four continued fractions, for , have an odd period.
How many continued fractions for have an odd period?
Input contains an integer
Print the answer corresponding to the test case.