Problem Description

当光头强还在当森林管理员的时候，他在一本武林秘籍中（据后来考证，估计是大计基——大学计算机基础），狂汗-ing），发现了神奇的二进制数。

如果一个正整数 $m$ 表示成二进制，它的位数为 $n$（不包含前导 $0$），光头强称它为一个 $n$ 二进制数。所有的 $n$ 二进制数中，$1$ 的总个数被称为 $n$ 对应的光头数。

例如，$3$ 二进制数总共有 $4$ 个，分别是 $4(100)、5(101)、6(110)、7(111)$，他们中 $1$ 的个数一共是 $1＋2＋2＋3=8$，所以 $3$ 对应的光头数就是 $8$。

Input

给你一个整数 $T$，表示输入数据的组数，接下来有 $T$ 行，每行包含一个正整数 $n\ (1 \leq n \leq 20)$。

Output

对于每个 $n$ ，在一行内输出n对应的光头数。

Samples

3
1
2
3

1
3
8