마트리곤

마트료시카는 한 세기도 더 전에 러시아에서 유래한 인형의 한 종류이다. 마트료시카의 뚜렷한 특징은 모두 크기가 서로 다른 인형들의 집합으로 이루어져 있으며, 작은 인형이 큰 인형 안에 꼭 맞게 들어간다는 것이다.

이 문제에서는 이와 비슷한 중첩 형태를 따르는 정볼록다각형들의 집합인 마트리곤을 다룬다. 마트리곤은 넓이가 양수인 정볼록다각형 $p_1, p_2, \dots, p_k$의 집합으로, 모든 $i$에 대해 $p_{i+1}$의 꼭짓점들이 $p_i$의 꼭짓점들의 진부분집합과 겹친다($p_{i+1}$의 꼭짓점 수는 $p_i$보다 엄격히 적다).

예를 들어, 다음 그림은 두 마트리곤을 보여 준다. 첫 번째 마트리곤에는 정이십사각형($24$개의 변), 정육각형($6$개의 변), 정삼각형($3$개의 변)이라는 $3$개의 정볼록다각형이 들어 있다. 두 번째 마트리곤에는 정이십이각형($22$개의 변)과 정십일각형($11$개의 변)이라는 $2$개의 정볼록다각형이 들어 있다. 이 마트리곤들은 각각 그 안의 모든 다각형을 합쳐 총 $33$개의 변을 가진다.

고정된 총 변의 수 $\mathbf{N}$가 주어질 때, 그 안의 모든 다각형의 변의 총수가 정확히 $\mathbf{N}$인 마트리곤에 포함될 수 있는 다각형 수의 최댓값을 계산한다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$.

테스트 세트 1 (Visible Verdict)

시간 제한: 20초. $3 \le \mathbf{N} \le 1000$.

테스트 세트 2 (Visible Verdict)

시간 제한: 40초. $3 \le \mathbf{N} \le 10^6$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 줄이 주어진다. 각 줄은 하나의 테스트 케이스를 나타내며, 목표로 하는 총 변의 수인 정수 $\mathbf{N}$ 하나를 포함한다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 그 안의 모든 다각형의 변의 총수가 정확히 $\mathbf{N}$인 마트리곤에 포함되는 다각형 수의 최댓값이다.

문제 설명의 첫 번째 그림에 나온 마트리곤은 예제 케이스 #1의 최적해이다.

예제 케이스 #2에서는 정십각형($10$개의 변) 안에 정오각형($5$개의 변)을 넣어 두 개의 다각형을 만들 수 있다.

예제 케이스 #3에서는 여러 정다각형으로 마트리곤을 만들 방법이 없으므로, 유일한 선택지는 정사십일각형($41$개의 변) 하나를 사용하는 것이다.