## COMBD - Combinatorial Sequence

no tags

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 containg the value of n.(n<=100000)

### Output

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

### Example

```Input:
212Output:23
``` Martin Dendis: 2013-12-12 13:49:14 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) (Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-09-04 04:41:09 too easy :P