34004번 - 메이플스토리2 장례식

문제

묘비와 비석 앞에서 춤을 추는 pichulia 의 메이플스토리2 캐릭터

"안녕하세요. 무슨 축제인가요?"

"아니요. 메이플스토리2 장례식입니다."

메이플스토리 게임의 흥행에 맞춰서 2015년 7월 7일에 야심 차게 오픈했던 메이플스토리2는 2025년 5월 29일 자로 서비스를 종료한다.

2차원에서 움직이던 메이플스토리와는 다르게, 메이플스토리2는 3차원에서 3D 캐릭터가 움직이며, 지형지물도 모두 3차원으로 이루어져 있다.

메이플스토리2의 열렬한 플레이어였던 pichulia는 나흘 뒤에 열릴 장례식을 준비하며 메이플스토리2의 특성에 맞게 3차원으로 묘비를 만들고자 한다. 우선 단위길이의 정육면체 블록을 $N$ 개 준비한 뒤, 각 블록의 면을 이어 붙여서 3D 묘비를 만들 것이다.

물론 묘비를 그냥 만들면 재미가 없기 때문에, 겉넓이가 최소가 되는 묘비를 만들어서 메이플스토리2의 넋을 기리고자 한다.

블록의 개수 $N$ 이 주어졌을 때, 이 $N$ 개의 블록으로 만들 수 있는 묘비의 겉넓이 최솟값을 구해보자.

입력

첫 번째 줄에는 테스트 케이스의 개수 $T$ 가 입력으로 주어진다. (1ドル \le T \le 10$)

이후 $T$ 줄에 걸쳐 블록의 개수 $N$ 이 주어진다. (1ドル \le N \le 1,000円,000円$)

입력으로 주어지는 모든 $N$들의 합은 1ドル,000円,000円$보다 작거나 같다.

출력

테스트 케이스마다 겉넓이의 최솟값을 $T$ 줄에 걸쳐 한 줄에 하나씩 출력한다.

제한

노트

$N$ 이 6ドル$ 일 때 겉넓이가 최소가 되는 모습.

N이 6일 때 3x2x1 직육면체, 또는 2x2x1 위에 블록 두 개를 추가한 모습

$N$ 이 19ドル$ 일 때 겉넓이가 최소가 되는 모습.

N이 19일 때 3x3x2 직육면체 위에 블록을 하나 추가한 모습