Matrygons

마트료시카는 100여 년 전 러시아에서 시작된 인형이다. 이 인형의 특징은 크기가 모두 다른 인형들의 집합으로 이루어져 있으며, 작은 인형이 큰 인형 안에 잘 들어맞는다는 것이다.

이 문제에서는 비슷한 중첩 구조를 따르는 정볼록다각형들의 집합인 마트리곤(matrygon)을 다룬다. 마트리곤은 양의 넓이를 가지는 정볼록다각형 p1, p2, …, pk의 집합으로, 모든 i에 대해 pi+1의 꼭짓점들이 pi의 꼭짓점들의 진부분집합과 겹친다(pi+1은 pi보다 꼭짓점 수가 엄격히 적다).

예를 들어, 다음 그림은 두 개의 마트리곤을 보여준다. 첫 번째는 정이십사각형(24변), 정육각형(6변), 정삼각형(3변)의 3개의 정볼록다각형을 포함한다. 두 번째는 정이십이각형(22변)과 정십일각형(11변)의 2개의 정볼록다각형을 포함한다. 이 마트리곤들은 각각 포함된 모든 다각형의 변의 수 합이 33이다.

총 변의 수 N이 주어질 때, 포함된 모든 다각형의 변의 수 합이 정확히 N인 마트리곤에 포함될 수 있는 다각형의 최대 개수를 구하라.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 다음 T개의 줄이 이어지며, 각 줄은 하나의 테스트 케이스를 나타내고 목표 총 변의 수인 정수 N을 포함한다.

각 테스트 케이스에 대해 Case #x: y를 한 줄에 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 포함된 모든 다각형의 변의 수 합이 정확히 N인 마트리곤의 다각형 최대 개수이다.

• 1 ≤ T ≤ 100.

문제 지문에 나온 첫 번째 마트리곤은 샘플 케이스 #1의 최적해이다.

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

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