32256번 - Super Shy (Hard)

일렬로 배치된 빈 좌석 $N$개가 있고, 사람들이 한 명씩 차례대로 앉으려고 한다.

사람들은 부끄러움을 많이 타기 때문에 현재 앉아 있는 사람과 최대한 멀리 떨어져 앉으려고 한다. 구체적으로, 앉을 수 있는 좌석은 아래 규칙을 따른다.

• 만약 먼저 앉은 사람이 아무도 없을 경우 아무 자리에나 앉을 수 있다.
• 만약 먼저 앉은 사람이 있고 바로 옆 자리에 사람이 없는 좌석이 있다면, 그러한 좌석들 중 가장 가까운 사람과의 거리가 가장 먼 자리들 중 한 곳에 앉을 수 있다.
• 만약 먼저 앉은 사람이 있고 바로 옆 자리에 사람이 없는 좌석이 없다면, 더 이상 앉을 수 없다.

이 사람들은 부끄러움이 많기는 하지만 동시에 공익을 추구하는 착한 사람들이기 때문에, 이러한 조건을 만족하는 자리들 중에서 결과적으로 최대한 많은 사람이 앉을 수 있는 자리를 선택할 것이다.

좌석의 수 $N$이 주어질 때 앉을 수 있는 최대 사람 수를 구하여라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. ($1\leq T\leq 100\, 000$)

둘째 줄부터 $T$개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 테스트 케이스의 첫째 줄에는 좌석의 수 $N$이 주어진다. ($1\leq N\leq 10^{18}$)

각 테스트 케이스에 대해, 앉을 수 있는 최대 사람 수를 출력한다.