#1163 벌집

44  1 s   128 MB  

Description

 

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1 씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N 이 주어졌을 때, 벌집의 중앙 1 에서 N 번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3 개, 58까지는 5 개를 지난다.

 

 

 

Input

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 15)가 주어진다. 각 테스트 케이스로는 한 줄에 하나의 방 번호 N (1 ≤ N ≤ 1,000,000)이 주어진다.

 

 

Output

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대해서 입력에서 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 한 줄에 하나씩 출력하시오.

 

 

Sample Input

Sample Output

3
13
58
120
3
5
7