Nikhil is a big fan of the Fibonacci series and often presents puzzles to his friends. Today, he came up with an interesting problem which is as follows:
Given a number K, find the smallest N for which Fib(N) has at least K digits. Also, compute the sum of its first and last digit.
Assume Fib(0) = 0, Fib(1) = 1, Fib(2) = 1 and so on.
Fib(n)=Fib(n-1)+Fib(n-2) for n>1
Input Format:
The first line contains T, the number of test cases.
Each of the subsequent T lines contains an integer K.
Output Format:
Print T lines of output, where each line has 2 space separated integers denoting the value of N satisfying above conditions and S, the sum of first and last digits of the Nth Fibonacci number.
Constraints:
1 <= T <= 100000
1 <= K <= 10^9
When K=1, the smallest N for which Fib(N) contains at least 1 digit is 0. Here, first and last digits are same and equal to 0. So, the sum is 0+0=0.
Similarly, when K=2, the smallest N = 7 which satisfies required conditions. Fib(7) = 13 and sum of the first and last digit is 1+3=4.
