URI Online Judge | 1202

White Nights Festival

By Marcel K. de C. Silva  Brazil

Timelimit: 1

Every year, at the time of the so-called "white nights" when the sun does not set over the city of St. Petersburg is the "festival of arts of White Nights", which consists of a series of musical performances, concerts, ballets, and attracting more artists around the world.


It is considered one of the greatest demonstrations of all Russia, since the height of the white nights, the festival usually has up to one million participants roaming the city streets. The Mariinsky Theatre hosts some of the best shows and, since no tickets enough for everyone who wants to watch 'performances, often using a system curious and fun raffle for those who may enter the theater.


Each person entering the theater, interested in attending a presentation chooses a row in which I would sit and receives a card with a number from 000 to 999 written on it. This number is the code of the draw that person. Arriving `entry clerk verifies the situation queue in which the person sit. The line is described by a sequence of '1 's and '0' s, where 1 indicates free chair seat and 0 indicates busy. This sequence is then interpreted as a binary representation of the number n. The person enters with his entourage if the nth number of the Fibonacci sequence ends exactly with the number written on your card. Thus, for example, if the description of row 100 is not enter if the person owning the card with the number 003.

Input

The input is composed of several instances. The first line of input contains an integer T indicating the number of instances. Each instance consists of a line containing a description of row with up to 10000 digits. The description of a row is a sequence of  '1' s and '0' s, never starting with '0' (the first chair of all ranks are reserved).

Output

For each instance print the 3 digits that must be written in the permission card that the person uses to entering the theater.

Sample Input Sample Output

3
1
10
1010

001
001
055

Note: be a positive integer written in decimal base. The n-th number, f (n) of the Fibonacci sequence is defined as follows: