题目描述

贺云艾 很喜欢欧几里得算法。欧几里得算法是一种用来求最大公约数的常用算法，它的一种 C++ 递归实现如下：

int gcd(int a, int b) {
	if (b == 0) {
		return a;
	} else {
		return gcd(b, a % b);
	}
}

现在我们已知 gcd(a, b) 这个函数共递归了 $n$ 次，求所有满足 $a > b \ge 0$ 的可能的 $a,\ b$ 中 $a + b$ 最小的一组的 $a$ 与 $b$ 之和。

你需要处理 $T$ 组询问，也就是对 $T$ 个不同的 $n$ 给出 各自 的 $a + b$ 的最小值。

输入格式

第一行一个正整数 $T$ ，表示共有 $T$ 组询问。

接下来 $T$ 行，每行一个非负整数 $n$ 。

输出格式

输出 $T$ 行，每行一个整数，表示 $a + b$ 的最小值。

样例

样例输入1

1
0

样例输出1

1

样例输入2

1
1

样例输出2

3

数据范围与提示

$1 \le T \le 81$

$0 \le n \le 80$

提示：

对于样例1，考虑 gcd(1, 0) ，由于 $b = 0$ ，不会递归，即是递归 $0$ 次。

对于样例2，考虑 gcd(2, 1) ，会递归一次至 gcd(1, 0) 。