FIBONACCI RIGHT ANGLED TRIANGLE | Code vita 2017

The Fibonacci series 1,1,2,3,5,8,... is well known. In this series, if F_n is the n^th number

F₁=1, F₂=1, F_n=F_n-1+F_n-2

Every alternate number in the series stating with 5 (5,13,34,...) can be the hypotenuse of a right angled triangle. We call each of these a Fibonacci Right Angled Triangle, or FRAT for short. The larger of the remaining two sides is the nearest integer to (2/sqrt(5)) times the hypotenuse.

A factor of a positive integer is a positive integer with divides it completely without leaving a remainder. For example, for the number 12, there are 6 factors 1, 2, 3, 4, 6, 12. Every positive integer k has at least two factors, 1 and the number k itself.

The objective of the program is to find the number of factors of the even side of the smallest FRAT whose hypotenuse is odd and is larger than a given number

Input
The input is a positive integer N

Output
The number of factors of the even side of the smallest FRAT which has an odd hypotenuse greater than N

Constraints
The even side is less than 5000000

Example 1

Input:

10

Output:
6

Explanation:
The smallest FRAT that has an hypotenuse greater than 10 is (13,12,5). As the hypotenuse is odd, we take this. The even side is 12, factors are (1,2,3,4,6,12), a total of 6 factors. The output is 6

Example 2

Input:

20

Output:

10

Explanation:
The smallest FRAT that has an hypotenuse greater than 20 is (34,30,16). As the hypotenuse is even, we take the next FRAT, which is (89,80,39). The even side is 80, factors are (1,2,4,5,8,10,16,20,40,80), a total of 10 factors. The output is 10