Fibo was a Famous Farmer. Who lived in the city of Fibonacia. One day while Farming For Fibonuts he saw a golden Fiboegg. He thought that now he will become a rich man with this golden Fiboegg. That night while he was sleeping a Fairy came in his dream and asked him did the Fiboegg came first or the golden Fibohen. So now come to the point: the Fibonacci series is a series in which every term is the sum of the previous two terms.
e.g. 0 1 1 2 3 5 8 13 ...

Your task is to print the SUM of the first N Fibonacci terms.

Input

First line of input will contain number of test cases T (<=1000), followed by T lines.
Every line will contain a positive integer N (<=90).

Output

For every input print the sum of first N Fibonacci numbers.

Example

Input:
2
5
8

Output:
7
33