## Algorithm

A. Phoenix and Balance
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Phoenix has n coins with weights 21,22,,2n21,22,…,2�. He knows that n is even.

He wants to split the coins into two piles such that each pile has exactly n2�2 coins and the difference of weights between the two piles is minimized. Formally, let a denote the sum of weights in the first pile, and b denote the sum of weights in the second pile. Help Phoenix minimize |ab||�−�|, the absolute value of ab�−�.

Input

The input consists of multiple test cases. The first line contains an integer t (1t1001≤�≤100) — the number of test cases.

The first line of each test case contains an integer n (2n302≤�≤30n is even) — the number of coins that Phoenix has.

Output

For each test case, output one integer — the minimum possible difference of weights between the two piles.

Example
input
Copy
2
2
4

output
Copy
2
6

Note

In the first test case, Phoenix has two coins with weights 22 and 44. No matter how he divides the coins, the difference will be 42=24−2=2.

In the second test case, Phoenix has four coins of weight 224488, and 1616. It is optimal for Phoenix to place coins with weights 22 and 1616 in one pile, and coins with weights 44 and 88 in another pile. The difference is (2+16)(4+8)=6(2+16)−(4+8)=6.

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

<#include<bits/stdc++.h>
using namespace std;

int main(){
int t;
cin>>t;
int n;
int arr[30];
int r = 2;
for(int i = 0; i < 30; i++){
arr[i] = r;
r *= 2;
}
while(t--){
cin>>n;
int asum(0), bsum(0);
for(int i = 0; i < n/2-1; i++){
asum += arr[i];
}
asum += arr[n-1];
for(int i = n/2 - 1; i < n-1; i++){
bsum += arr[i];
}
int diff = asum - bsum >= 0 ? (asum - bsum) : (bsum - asum);
cout<<diff<<endl;
}
return 0;
}
Copy The Code &

Input

cmd
2
2
4

Output

cmd
2
6