Frogger

무한한 xy 격자 위에 개구리 떼가 앉아 있다. 모든 개구리의 x 좌표는 $0$ 이하다. 격자점 $(2, 0)$에는 파리 한 마리가 앉아 있고, 배고픈 개구리들은 거기까지 가서 파리를 먹으려 한다. 걸림돌이 하나 있다. 개구리는 바로 옆 칸에 앉은 다른 개구리를 뛰어넘어 그 바로 다음 칸으로 가는 방식으로만 움직일 수 있고, 뛰어넘긴 개구리는 터져서 사라진다. 그래서 $(0, 0)$에 피터가 앉아 있으면 $(-1, 0)$의 존은 $(1, 0)$으로 뛸 수 있지만, 그 대가로 피터는 터져 없어진다. 같은 식으로 $(-1, 2)$의 알프레드는 $(-1, 1)$에 바니가 앉아 있을 때 $(-1, 0)$으로 뛸 수 있고, 바니는 터진다.

점프는 상하좌우 네 방향 중 하나로만 한다. 뛰어넘는 칸에는 개구리가 있어야 하고, 착지하는 칸은 비어 있어야 한다.

파리까지 가는 데는 개구리 목숨이 많이 든다. 그래도 개구리들은 공동의 이익을 믿고 모든 것을 내놓을 각오가 되어 있다. 남은 질문은 도달 자체가 가능한지다. 파리가 음이 아닌 x축의 점 $(X, 0)$에 있을 때, 처음에 개구리가 몇 마리 있어야 하는지 구하라. 개구리는 처음에 y축 위나 그 왼쪽, 즉 x 좌표가 $0$ 이하인 격자점 어디에나 놓을 수 있고, 두 개구리가 같은 위치에 있으면 안 된다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. $T \le 100$이다.

각 테스트 케이스는 한 줄이고, 정수 $X$ 하나가 주어진다. $0 \le X \le 31$이며, 파리는 $(X, 0)$에 있다.

각 테스트 케이스마다 파리를 잡기 위해 처음에 필요한 개구리의 최소 마릿수를 한 줄에 출력한다. 파리를 잡는 것이 불가능하면 그 줄에 frogger를 출력한다.