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
sgc_072: 2017-09-04 13:31:42

The question's name is tricky :P

arikpamnani: 2017-07-28 22:06:01

3 lines in Python :p

hunnychauhan: 2017-07-19 13:49:59

easy with pen paper....

losmi247: 2017-06-09 17:41:35

Guys, heres a tip:
pen and paper!
:)

amulyagaur: 2017-05-19 07:08:12

@akayushi.... modulo 6 trick may be of some help

Last edit: 2017-05-19 07:08:42
akayushi: 2017-05-14 12:49:51

i am getting wrong answer..someone give me some hint

holmesherlock: 2017-04-01 00:41:11

printf ,scanf gave WA,,

vengatesh15: 2017-02-12 18:37:03

easy one with pen and paper

kass_97: 2017-01-06 12:23:52

Just requires pen and paper to solve :p


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