Description

It is said that someone received the blessing from Fibonacci when he was dreaming. Fibonacci gave a hint to find the answer to the life, universe and everything in the Fibonacci sequence. The well-known Fibonacci sequence is defined as following: F(0)=f(1)=1 F(n)=F(n-1)+f(n-2) n>1 We regards n as the index of the Fibonacci number F(n). Fibonacci gives only some digits of a Fibonacci number. You are very interesting about this story and start to study on the Fibonacci numbers. To start your research, you decide to write a program to determine the smallest index of the smallest Fibonacci number that ends with the given digits.

Input

The input file contains multiple test cases. The first line of input contains only one integer denoting the number of test cases. For each case, input contains a single line with no more than five digits which is the request of Fibonacci.

Output

For each test case, output a single integer that is the smallest index of the smallest Fibonacci number that ends with the given digits. If such Fibonacci number does not exist, output -1 instead. See the sample output for further output format information.

Sample

Input

2
2
3

Output

2
3

Hint

参照斐波追溯数

Source: ACM2011亚洲预赛上海赛区热身题