Initialize 1, 2, 4, 8, 16, 32

Source: C Primer Plus

Version: Phuoc Hung OJ Extended

Problem Statement

Consider the fully initialized array

int a[6] = {1, 2, 4, 8, 16, 32};

There are $q$ queries. Each query provides an index $p$ in $[0,5]$. Print $a_p$.

Input

• The first line contains $q$.
• The second line contains exactly $q$ indices $p_1,p_2,\ldots,p_q$, each in $[0,5]$.

Output

For each query, print the corresponding array element on its own line.

Subtasks

Subtask 1 (20 points): $1\le q\le2$.

Subtask 2 (30 points): $1\le q\le6$ and no index is repeated.

Subtask 3 (50 points): $1\le q\le100$; indices may repeat.

Examples

Input

5
0 2 5 3 1

Output

1
4
32
8
2

Explanation

The array is $a=(1,2,4,8,16,32)$. The queried indices are $0,2,5,3,1$, so the corresponding values are $1,4,32,8,2$.