COMBD - Combinatorial Sequence

Your task is to evaluate  the following series for a given n

2^n - ((n-1)C(1))*2^(n-2)  + ((n-2)C(2))*2^(n-4) - ((n-3)C(3))*2^(n-6)+ ...

(n)C(r) denotes n choose r.

Power of 2 is always non-negative.(i.e. series terminates when either power of 2 goes negative or combinatorics becomes undefined.)

Input

First line of input contains the number of test cases (t <= 100000), then follows t lines, each containing the value of n (n <= 100000.)

Output

You should output t lines, ith line contains answer of the ith test case

Example

Input:
2
1
2

Output:
2
3

Click here to see my set of problems at Spoj.


Added by:devu
Date:2012-07-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2013-12-12 13:49:14 Martin Dendis
Yes, It really is :)
The biggest problem is with reading input, because you have to be really fast.
For those, who prefer programming in JAVA, you have to use C/C++ or another language.
Java can't handle it! (Or at least I was unable to pass through time limit with JAVA)
2013-09-04 04:41:09 (Tjandra Satria Gunawan)(曾毅昆)
too easy :P
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.