The nth 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.

Input

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 232-1 (inclusive). There may be leading zeros in the coded numbers.

Output

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".

Sample Input
5
1
000000000000000010
100001000
10110110
1111111111111111111111111
Sample Output
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