This problem is a programming version of Problem 25 from projecteuler.net
The Fibonacci sequence is defined by the recurrence relation:
.
Hence the first 12 terms will be:
The term, , is the first term to contain three digits.
What is the first term in the Fibonacci sequence to contain digits?
Input Format
The first line contains an integer , i.e., number of test cases.
Next lines will contain an integer .
Constraints
Output Format
Print the values corresponding to each test case.
Sample Input
2
3
4
Sample Output
12
17