Problem hidden

COMBD - Combinatorial Sequence

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

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

Where (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.


Adicionado por:devu
Data:2012-07-04
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Own Problem
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.