지루함 해소 (Hard)

길리언은 평소에 매우 활발한 아이다. 대부분의 시간을 친구들과 놀며 장난을 치려고 한다. 그러나 오늘은 다르다. 길리언은 독감에 걸려 침대에서 꼼짝 않고 지루하게 누워 있어야 한다. 오빠가 그녀를 즐겁게 해 주려고 다음 게임을 생각해 냈다.

길리언이 1보다 큰 정수 $x$를 가지고 있을 때, 그녀는 $x$를 $x = y + z$를 만족하는 두 양의 정수 $y$와 $z$로 나눌 수 있다. 이 연산을 수행하면 오빠는 그녀에게 $y \cdot z$개의 헤이즐넛을 준다. 하지만 모든 $y$, $z$ 쌍이 유효한 것은 아니며, 길리언은 지켜야 하는 규칙이 있다. 이 규칙은 쉬운 하위 문제와 어려운 하위 문제에서 서로 다르며, 아래 문제 명세 부분에 나열되어 있다.

이 연산으로 얻은 수도 다시 나눌 수 있다. 게임을 시작할 때 길리언은 정수 $n$ 하나를 가지고 있다. 그녀는 1이 정확히 $n$개 남을 때까지 연산을 반복한다. 그녀가 현명하게 선택한다면 얻을 수 있는 헤이즐넛의 최댓값은 얼마인가?

길리언은 $1 < k \le x$를 만족하는 임의의 정수 $k$를 고를 수 있으며, $x$를 $y = \lfloor x/k \rfloor$와 $z = x - \lfloor x/k \rfloor$로 나눈다.

입력 파일의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 $t$ ($t \le 1000$)가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 하나 있다.

각 테스트 케이스는 길리언의 초기 정수 $n > 1$이 적힌 한 줄로 이루어진다. $n \le 10^9$이라고 가정해도 된다.

각 테스트 케이스마다 헤이즐넛의 최댓값을 한 줄에 출력한다.