색칠 게임

John은 컴퓨터 게임을 즐겨 한다. 그는 최근 흥미로운 게임을 발견했다. 게임에는 $\mathbf{N}$개의 칸이 있으며, 이 칸들은 왼쪽에서 오른쪽으로 한 줄로 배열되고 $1$부터 시작하는 연속된 정수로 번호가 매겨져 있다. 처음에는 모든 칸이 흰색이다. 어떤 칸이 흰색이고 그 칸에 인접한 빨간색 칸이 하나도 없다면 그 칸은 유효하다. 매 턴에 플레이어는 유효한 칸 중 아무 칸이나 빨간색으로 칠한다. 유효한 칸이 하나도 남지 않으면 게임이 끝난다. 플레이어의 점수는 자신이 칠한 칸의 수와 같다.

게임을 숙달하기 위해 John은 봇을 상대로 연습하고 있다. 봇은 제대로 훈련되지 않아 항상 왼쪽에서 첫 번째 유효한 칸을 칠한다. 반면 John은 매우 신중하게 게임을 하며 유효한 칸 중 아무 칸이나 선택할 수 있다. 봇이 먼저 움직이고, 두 플레이어는 번갈아 가며 턴을 진행한다.

John이 상대의 점수를 최소화하도록 최적으로 플레이한다고 할 때, 봇이 달성할 수 있는 최대 점수를 구한다.

제한

시간 제한: 20초. 메모리 제한: 1 GB.

테스트 세트 1

$1 \le \mathbf{T} \le 6$. $1 \le \mathbf{N} \le 6$.

테스트 세트 2

$1 \le \mathbf{T} \le 100$. $1 \le \mathbf{N} \le 10^6$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 유일한 줄에는 게임의 칸 수를 나타내는 정수 $\mathbf{N}$이 주어진다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이고(1부터 시작), $y$는 John이 최적으로 플레이할 때 봇이 달성할 수 있는 최대 점수이다.

예제 케이스 #1에는 $\mathbf{N} = 1$개의 칸이 있다. 봇이 달성할 수 있는 최대 점수는 $1$이다.

• 첫 번째 수: 봇이 첫 번째 칸을 빨간색으로 칠한다.

더 이상 가능한 수가 없으므로 게임이 끝난다. 따라서 정답은 $1$이다.

예제 케이스 #2에는 $\mathbf{N} = 3$개의 칸이 있다. 봇이 달성할 수 있는 최대 점수는 $1$이다.

• 첫 번째 수: 봇이 첫 번째 칸을 빨간색으로 칠한다.

• 두 번째 수: John이 세 번째 칸을 빨간색으로 칠한다.

더 이상 가능한 수가 없으므로 게임이 끝난다. 따라서 정답은 $1$이다.

예제 케이스 #3에는 $\mathbf{N} = 6$개의 칸이 있다. 봇이 달성할 수 있는 최대 점수는 $2$이다. 이 예제에는 여러 해답이 존재하며, 그중 하나는 다음과 같다.

• 첫 번째 수: 봇이 첫 번째 칸을 빨간색으로 칠한다.

• 두 번째 수: John이 세 번째 칸을 빨간색으로 칠한다.

• 세 번째 수: 봇이 다섯 번째 칸을 빨간색으로 칠한다.

더 이상 가능한 수가 없으므로 게임이 끝난다. 따라서 정답은 $2$이다.