Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden

ESYRCRTN - Why Always Recursion


 

  • 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

Added by:Murad
Date:2016-04-02
Time limit:0.5s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:None