Fibonacci Sequence Position Finder

You are given an integer n. Your task is to determine the position of n in the Fibonacci sequence if it appears exactly as a Fibonacci number, and output the 0-based position if n = 0 and the 1-based position for positive numbers. If n is not a Fibonacci number, output -1.

The Fibonacci sequence is defined as follows:

\(F(0) = 0\), \(F(1) = 1\) and for \(n \ge 2\), \(F(n) = F(n-1) + F(n-2)\).

For example:

• For n = 21, the position is 8 since \(F(8)=21\).
• For n = 14, 14 is not a Fibonacci number so the output is -1.
• For n = 0, the output is 0.
• For n = 1, the output is 1. (Return the first occurrence of 1)
• For n = 144, the output is 12.

You will need to process several test cases.

inputFormat

The first line contains an integer T (the number of test cases). This is followed by T lines, each containing a single integer n for which you need to determine the Fibonacci position.

Input Format:

T
n1
n2
...
nT

outputFormat

For each test case, output a single line containing the position of the given number in the Fibonacci sequence. If the number is not a Fibonacci number, output -1.

Output Format:

result1
result2
...
resultT

## sample

3
21
14
0

8
-1
0

</p>