마법의 백합 우물

숲속에는 수면에 백합이 몇 송이 떠 있는 깊고 마법 같은 우물이 있다. 여러분은 커다란 빈 바구니와 동전 몇 개를 가지고 우물 옆에 서 있다. 여러분은 우물에 있는 백합의 수보다 많은 동전을 가지고 있다. 우물은 여러분의 바구니가 비어 있다는 사실을 기억해 두었다.

동전 한 개를 우물에 던지면 우물은 백합 한 송이를 여러분의 바구니로 내보낸다. 동전 네 개를 한꺼번에 우물에 던지면 우물은 지금까지 여러분의 바구니로 내보낸 백합의 수를 기억해 둔다. 동전 두 개를 한꺼번에 우물에 던지면 우물은 마지막으로 기억해 둔 수만큼의 백합을 여러분의 바구니로 내보낸다. 동전 한 개 또는 동전 두 개를 한꺼번에 우물에 던졌을 때 우물에 남은 백합이 충분하지 않으면, 우물은 어떤 백합도 내보내지 않는다.

처음에 우물에 있는 백합의 수 $\mathbf{L}$이 주어질 때, 우물이 모든 백합을 여러분의 바구니로 내보내게 하기 위해 우물에 던져야 하는 동전의 최소 개수를 구한다.

제한

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

테스트 세트 1

$1 \le \mathbf{T} \le 20$. $1 \le \mathbf{L} \le 20$.

테스트 세트 2

$1 \le \mathbf{T} \le 100$. $1 \le \mathbf{L} \le 10^5$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 줄이 주어진다. 각 줄에는 처음에 우물에 있는 백합의 수를 나타내는 정수 $\mathbf{L}$ 하나가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며(1부터 시작), $y$는 우물이 $\mathbf{L}$송이의 백합을 모두 여러분의 바구니로 내보내게 하기 위해 우물에 던져야 하는 동전의 최소 개수이다.

테스트 케이스 #1에서 우물에 $5$송이의 백합이 있을 때 필요한 동전의 최소 개수는 $5$개이다. 동전을 한 번에 한 개씩 우물에 던지면 우물은 $5$송이의 백합을 한 번에 한 송이씩 바구니로 내보낸다. 이보다 더 나은 답을 얻는 다른 행동 순서는 없으므로 답은 $5$이다.

테스트 케이스 #2에서는 먼저 동전 $5$개를 한 번에 한 개씩 우물에 던지고, 우물은 백합 $5$송이를 한 번에 한 송이씩 바구니로 내보낸다. 다음으로 동전 $4$개를 한꺼번에 우물에 던지면, 우물은 지금까지 바구니로 백합 $5$송이를 내보냈다는 것을 기억해 둔다. 그런 다음 동전 $2$개를 한꺼번에 우물에 던지면 우물은 기억해 둔 수인 백합 $5$송이를 바구니로 내보낸다. 그다음 동전 $2$개를 다시 한꺼번에 우물에 던지면 우물은 백합 $5$송이를 추가로 바구니로 내보낸다. 마지막으로 동전 $2$개를 다시 한꺼번에 우물에 던지면 우물은 남은 백합 $5$송이를 바구니로 내보낸다. 필요한 동전의 총개수는 $15$개이다. $20$송이의 백합을 이보다 적은 수의 동전으로 우물에서 꺼내는 것은 불가능하므로 답은 $15$이다.