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 2Output: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 |