Description

给定一整数n, 写递归函数求2f(floor(n/2))+n, 其中floor(n/2)表示向下取整，f(0)=1, f(1)=1.

Input

输入第1行有一个int型正整数m (m<＝20), 表示有m行输入.
每行输入一个int型正整数n (1000<n<10000).

Output

输出m行, 每行为2f(floor(n/2))+n.

Sample Input

4
3
8190
9690
7246

Sample Output

5
98304
129844
89584