Frogger

A group of frogs sits on an infinite xy grid. Every frog has an x coordinate of $0$ or less. A fly sits on the grid point $(2, 0)$, and the hungry frogs want to get there and eat it. There is one catch. A frog can move only by jumping over another frog that sits next to it and landing on the square just beyond, and the frog that was jumped over explodes and is gone. So if Peter sits at $(0, 0)$, then John at $(-1, 0)$ can jump to $(1, 0)$, but Peter explodes. In the same way, if Alfred sits at $(-1, 2)$ and Barney sits at $(-1, 1)$, then Alfred can jump to $(-1, 0)$ and Barney explodes.

A jump goes in one of the four axis directions. The square that is jumped over must hold a frog, and the landing square must be empty.

Reaching the fly costs many frog lives. The frogs believe in the common good and are willing to give up everything for it. The remaining question is whether they can make it at all. Given the position $(X, 0)$ of the fly on the non-negative x axis, find how many frogs you need to start with. The frogs can be placed initially on any grid points on or to the left of the y axis, that is with an x coordinate of $0$ or less, and no two frogs may share a position.

The first line holds the number of test cases $T$, with $T \le 100$.

Each test case is one line with a single integer $X$, where $0 \le X \le 31$. The fly is at $(X, 0)$.

For each test case, print on one line the minimum number of frogs you need to start with in order to catch the fly. If catching the fly is impossible, print frogger on that line instead.