입이 떡 벌어지는 집합

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

요약

1 이상 n 이하의 정수 중 어느 두 원소도 서로를 나누지 않는 부분집합의 최대 크기를 구하고, 그 크기를 가지는 부분집합 중 원소 합이 최소인 값을 각 테스트마다 계산한다.

문제

집합 $\{1, 2, 3, \ldots, n\}$ 의 부분집합 $A$ 가 흥미롭다는 것은, $A$ 에 속한 서로 다른 두 정수 $x, y$ 에 대해 $x$ 가 $y$ 를 나누지도 않고 $y$ 가 $x$ 를 나누지도 않는다는 뜻이다.

흥미로운 부분집합 $A$ 가 놀랍다는 것은, 모든 흥미로운 부분집합 가운데 원소의 개수가 최대라는 뜻이다.

마지막으로, 놀라운 부분집합 $A$ 가 입이 떡 벌어진다는 것은, 모든 놀라운 부분집합 가운데 원소의 합이 최소라는 뜻이다.

$n$ 이 주어질 때, $\{1, 2, 3, \ldots, n\}$ 의 입이 떡 벌어지는 부분집합의 원소 합을 구한다.

첫째 줄에는 테스트 케이스의 수 $t$ 가 주어진다 ( $1 \le t \le 10^5$ ).

다음 $T$ 개의 줄에는 각각 정수 $n_i$ 가 주어진다 ( $1 \le n_i \le 10^9$ ).

각 테스트 케이스의 답을 한 줄에 하나씩 $T$ 줄에 걸쳐 출력한다.