F005A. Paraules de Fibonacci P50726

The words of Fibonacci $F_1, F_2, F_3, \dots$ are described in the following way:

• $F_1 =$ “a”.

• $F_2 =$ “b”.

• For every $n \ge 3$, $F_n$ is the result of concatenate $F_{n-2}$ with $F_{n-1}$.

The first seven words of the sequence of Fibonacci are: $F_1 =$ “a”, $F_2 =$ “b”, $F_3 =$ “ab”, $F_4 =$ “bab”, $F_5 =$ “abbab”, $F_6 =$ “bababbab” and $F_7 =$ “abbabbababbab”.

Your task is to write a program that, given a sequence of words, prints if they are Fibonacci words or they are not. For those that are it, you must indicate their position in the sequence.

Input

The input is a sequence of words only composed by the letters a and b. None of the words will have more than 1000 letters.

Output

For each Word, your program must indicate its position in the sequence, or print that it is not a word of Fibonacci, following the format of the instance.

Hint

Notice that the length of a word of Fibonacci increases very fast. Therefore, there are few words of Fibonacci having size 1000 or less (in fact, there are exactly 16). Calculate all of them at the beginning of the program.

Observations

• Remember that a string s with n characters c can be declared like this: string s(n, c);

• Remember also that the string operations like s += ’a’;, s1 += s2; or s = s1 + s2; are not allowed.