- All Contests
- ProjectEuler+
- Project Euler #64: Odd period square roots

# Project Euler #64: Odd period square roots

# Project Euler #64: Odd period square roots

_{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 Format**

Input contains an integer

**Constraints**

**Output Format**

Print the answer corresponding to the test case.

**Sample Input**

```
13
```

**Sample Output**

```
4
```