Given the ith (1<=i<=35) Fibonacci number F_i calculate the sum of the ith till i+9th number F_i+F_i+1+...+F_i+9 and the last digit of the i+246th one F_i+246.
Be careful: Your solution mustn't exceed 111 bytes. But rather half of it should be more than enough.
Score is source length.

Input

In the first line the number of testcases N<=100, then N lines with one positive integer i.

Output

One line with "F_i+F_i+1+...+F_i+9+last digit of F_i+246" for each i.

Example

Input:
2
1
35

Output:
146
1821381552