一群青蛙坐落在一个无限大的 $xy$ 网格上。所有青蛙的 $x$ 坐标均为非正数。在网格位置 $(2, 0)$ 处有一只苍蝇。青蛙们很饿，想要到达那里吃掉苍蝇。这里有一个限制：青蛙只能通过跳过旁边的一只青蛙来移动，且被跳过的青蛙会爆炸消失。例如，坐在 $(-1, 0)$ 的青蛙 John 可以跳到 $(1, 0)$，前提是 Peter 坐在 $(0, 0)$，但随后 Peter 会爆炸消失。类似地，如果 Alfred 坐在 $(-1, 2)$，Barney 坐在 $(-1, 1)$，那么 Alfred 可以跳到 $(-1, 0)$，而 Barney 会爆炸消失。

因此，到达苍蝇所在位置需要付出巨大的生命代价，但青蛙们都相信集体利益，并愿意为此牺牲一切。然而问题在于，它们是否真的能到达那里。给定苍蝇在非负 $x$ 轴上的位置，你需要初始时准备多少只青蛙？青蛙最初可以放置在 $y$ 轴上或 $y$ 轴左侧的任何位置，但必须占据不同的位置。

输入格式

第一行包含测试用例的数量 $T \le 100$。对于每个测试用例，有一行包含一个整数 $0 \le X \le 31$，表示苍蝇位于 $(X, 0)$。

输出格式

对于每个测试用例，输出一行，表示为了抓到苍蝇所需的最少青蛙数量，如果无法做到，则输出 “frogger”。

样例

输入 1

4
0
1
2
3

输出 1

1
2
4
8

Figure 1. 青蛙跳跃过程示意图