시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 115 85 69 82.143%

문제

새학기를 맞아 다이어트 중인 예찬이는 힘든 시간을 보내고 있다. 다이어트 중 너무 배가 고팠던 예찬이는 피자를 시켜 먹기로 한다. 피자 맛을 오래 느끼고 싶었던 예찬이는 피자를 k번 (1 ≤ k ≤ K) 의 칼질로 조각 낸 뒤, 조각을 하나하나 음미하려고 계획했다. 하지만 기다리던 피자가 도착하고 나서야 예찬이는 본인에게 칼이 없다는 사실을 알게 되었다. 때마침 칼이 있던 예찬이의 동기 윤희는 예찬이에게 다음과 같은 제안을 한다. 

“칼을 쓰게 해줄게! 하지만 피자를 다 자른 뒤에 칼질 한 번마다, 나한테 피자를 한 조각씩 증가 시키면서 줘. 다시 말해 칼질을 1번 하면 1조각을, 2번 하면 추가로 2조각을 얹어서 3조각을, 3번 하면 추가로 3조각을 얹어서 6조각을 달란말이야”

어차피 다이어트 중이었던 예찬이는 윤희의 제안이 나쁘지 않다고 생각해서 그 제안을 받아들이기로 한다. 하지만, 예찬이는 피자 맛을 오래도록 느끼고 싶기 때문에, 자신이 먹는 피자 조각의 수를 최대로 하고자 한다. 단, 피자 조각의 크기는 중요하지 않고, 칼질은 직선으로만 가능하다. 최대 칼질의 수 K가 주어질 때, 예찬이가 먹을 수 있는 최대 피자 조각 수를 구해주자!

입력

첫째 줄에는 테스트 케이스의 수 N이 정수로 주어진다. (1 ≤ N ≤ 1000)

다음 줄부터 N개의 줄에 테스트케이스가 한 줄에 하나씩 주어지고 각 테스트케이스에는 칼질의 최대 숫자 K이 정수로 주어진다. (1 ≤ K ≤ 109)

출력

각 테스트 케이스마다 예찬이가 먹을 수 있는 최대 피자 조각 수를 출력한다.

예제 입력 1

2
1
2

예제 출력 1

1
1

두 번째 테스트케이스 (K=2)의 경우, 예찬이는 최대 2번의 칼질을 할 수 있다.

칼질을 1번 할 경우, 피자는 2조각이되고 윤희에게 1조각을 줘야하므로 예찬이는 1조각을 먹을 수 있다.

칼질을 2번 할 경우, 피자는 최대 4조각이 되고 윤희에게 1+2=3 조각을 줘야하므로 예찬이는 역시 1조각을 먹을 수 있다.

따라서 두 번째 테스트케이스의 정답은 1이 된다.