30704번 - 정사각형 연결하기

문제

한 변의 길이가 1ドル$인, 모양과 크기가 같은 정사각형 모양의 타일이 $N$장 주어진다. 그리고 한 변의 길이가 1ドル$인 정사각형들로 이루어진 격자가 그려진 바닥이 있다. 이 바닥에 타일들을 이어 붙여 하나의 도형을 만들자.

타일은 격자판의 각 칸에 맞춰서만 붙일 수 있으며, 타일끼리 겹치거나 포갤 수 없다. 또 모든 타일은 서로 연결되어 있어야 한다.

정사각형 타일의 장수가 주어지면, 이들을 위에서 설명한 규칙에 맞게 이어 붙여 만들 수 있는 도형 둘레의 최솟값을 구하여라. 하나의 입력에서 $T$개의 테스트 케이스를 해결해야 한다.

입력

첫 번째 줄에 테스트 케이스의 수 $T$가 주어진다.(1ドル\leq T\leq 100,000円$)

이후 $T$개 줄에 걸쳐 각 테스트 케이스마다 주어진 타일의 수 $N$이 주어진다.(1ドル\leq N\leq 10^9$)

입력되는 데이터의 양이 많음에 유의하자.

출력

테스트 케이스가 주어진 순서대로, 각 테스트 케이스마다 가능한 둘레 길이의 최솟값을 한 줄에 하나씩 출력한다.

제한

힌트

하나의 입력에서 같은 문제를 여러 번 푸는 형식의 문제이다. 시간 제한 안에 입력으로 주어진 모든 테스트 케이스에 대해 답을 바르게 출력하고 프로그램을 종료해야 정답으로 인정함에 유의하라.