The n^{th} element of the famous Fibonacci sequence (or Fibonacci numbers), can be computed recursively by the following formula,

It has been proved that, an arbitrary non-negative integer can be coded using Fibonacci numbers (F(0) is not used), but such coding may not be unique, for example,

However, it might be unique if we add some restrictions. We name a Standard Fibonacci coding of integers, in which consecutive Fibonacci numbers are NOT used in a single code. As with (100001000)_{f} in the previous example, who does not have consecutive 1's.

Write a program, given the Fibonacci code of an integer, to (a) compute the decimal equivalent of that integer, and (b) convert the Fibonacci code to its standard form when necessary.

The first line of the input is an integer N (0<N<15000). Each of the following N lines contains a coded integer, whose decimal value falls between 0 and 2^{32}-1 (inclusive). There may be leading zeros in the coded numbers.

For each input, write a line containing the decimal equivalent of the input integer, followed by its standard Fibonacci coding. If the input code is already in its standard form, output "already in standard form".

5 1 000000000000000010 100001000 10110110 1111111111111111111111111

1 in decimal, already in standard form 2 in decimal, already in standard form 60 in decimal, already in standard form 60 in decimal, whose standard form is 100001000 317809 in decimal, whose standard form is 10101010101010101010101001