4. Fibonacci Spiral

What is the Problem?

The Fibonacci sequence can be represented as follows:

• The first two Fibonacci numbers, F(1) and F(2), are both equal to 1.

• For N > 2, the Nth Fibonacci number is the sum of the two previous ones, i.e.

F(N) = F(N-1) + F(N-2)

The first few terms of the sequence are 1, 1, 2, 3, 5, 8, 13, ...

An interesting way to represent this sequence is by starting as a square with a side length equal to F(1) and then repeatedly adding squares in clockwise order with the side length of the Nth square being equal to the F(N). By doing this, a rectangle will always be formed. Here is a diagram:

This process can be repeated indefinitely, which means that we can cover the plane using these Fibonacci squares. Suppose we repeat the process as shown in the diagram above with the top-left corner of the first square being the origin (0, 0).

Given a coordinate (X, Y), can you figure out which Fibonacci square the coordinate is in?

Input Specifications

DATA41.txt (DATA42.txt for the second try) will contain 10 datasets. Each dataset consists of two space-separated integers X, Y (-109 ≤ X, Y ≤ 109) representing a point on the plane.

Output Specifications

For each dataset, output the smallest integer N such that the point (X, Y) is contained (or is on the boundary of) a square of side length F(N).

Sample Input (5 Datasets Shown)

0 0

1 1

2 1

3 -2

-9 0

Sample Output

1

3

4

5

6