Project Euler #25: N-digit Fibonacci number

_{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