Count Binary Palindromes

Given an integer n, your task is to compute the number of binary palindromic strings of length n. A binary palindromic string is a string that reads the same backward as forward and consists solely of the characters '0' and '1'.

The answer can be mathematically formulated as follows:

• For n = 1, the answer is 2, as the strings are "0" and "1".
• For n > 1:
  • If n is even, then the number of binary palindromic strings is \(2^{\frac{n}{2}}\).
  • If n is odd, then the number is \(2^{\left(\frac{n}{2} + 1\right)}\), where the division is integer division.

You need to process multiple test cases.

inputFormat

The first line of input contains a single integer T representing the number of test cases. Each of the following T lines contains a single integer n denoting the length of the binary string.

outputFormat

For each test case, output the number of binary palindromic strings of length n on a separate line.## sample

3
1
2
3

2
2
4