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

hide comments
pkumar153: 2021-08-17 21:59:29

Just write down the first 6 terms and observe the pattern. Why always recursion??

Last edit: 2021-08-17 22:01:57
brain_sick: 2021-07-04 01:30:58

I did it by matrix exponentiation, any easier way to do it?

Last edit: 2021-07-04 01:31:13

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