Phoenix 有 $$$n$$$ 硬币,重量为 $$$2^1、2^2、\dots、2^n$$$。他知道 $$$n$$$ 是偶数。
他想将硬币分成两堆,使得每堆正好有 $$$\frac{n}{2}$$$ 硬币,并且两堆之间的重量差异最小化。形式上,让 $$$a$$$ 表示第一堆中的权重之和,$$$b$$$ 表示第二堆中的权重之和。帮助 Phoenix 最小化 $$$|a-b|$$$,即 $$$a-b$$$ 的绝对值。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$($$$2 \le n \le 30$$$;$$$n$$$ 为偶数)——Phoenix 拥有的硬币数量。
输出
对于每个测试用例,输出一个整数——两堆之间重量的最小可能差异。
示例
输入 #1
2 2 4
输出 #1
2 6
注意
在第一个测试用例中,Phoenix 有两个重量为 $$$2$$$ 和 $$$4$$$ 的硬币。不管他怎么分硬币,差额都是$$$4-2=2$$$。
在第二个测试用例中,Phoenix 有四枚重量为 $$$2$$$、$$$4$$$、$$$8$$$ 和 $$$16$$$ 的硬币。 Phoenix 的最佳选择是将重量为 $$$2$$$ 和 $$$16$$$ 的硬币放在一堆,将重量为 $$$4$$$ 和 $$$8$$$ 的硬币放在另一堆。差别是$$$(2+16)-(4+8)=6$$$。