파도반 수열

면접 대비

시간 제한1초메모리 제한128 MB

요약

나선 모양으로 이어 붙인 정삼각형의 변 길이로 정의되는 파도반 수열의 N번째 항을 각 테스트 케이스마다 구합니다.

문제

정삼각형을 나선 모양으로 이어 붙인다. 첫 삼각형은 한 변의 길이가 1인 정삼각형이다. 그 뒤로는 나선에서 가장 긴 변의 길이를 $k$ 라 할 때, 그 변에 한 변의 길이가 $k$ 인 정삼각형을 붙인다. 이 과정을 계속 반복한다.

파도반 수열 $P(N)$ 은 나선에 $N$ 번째로 놓인 정삼각형의 한 변의 길이다. $P(1)$ 부터 $P(10)$ 까지 첫 열 개의 값은 1, 1, 1, 2, 2, 3, 4, 5, 7, 9다.

$N$ 이 주어졌을 때, $P(N)$ 을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 각 테스트 케이스는 한 줄로 이루어지며, 정수 $N$ 이 주어진다. ( $1 \le N \le 100$ )

각 테스트 케이스마다 $P(N)$ 을 한 줄에 하나씩 출력한다.