• F(1) = 1
• F(2) = 3
• F(N) = F(N-1) - F(N-2)

Now you are given N, you have to find the value of F(1) + F(2) + ... + F(N).

Input

Input starts with an integer T (1 <= T <= 1000), denoting the number of test cases. Each test case contains an integer N (1 <= N <= 10^18).

Output

For each test case, print the value.

Example

Input:
2
1 
2

Output:
1
4