Super Shy (Hard)

일렬로 놓인 빈 좌석 $N$개가 있습니다. 사람들이 한 명씩 차례대로 앉으려고 합니다.

이 사람들은 부끄러움을 많이 타서, 이미 앉은 사람과 최대한 멀리 떨어져 앉으려고 합니다. 구체적으로 좌석은 다음 규칙을 따릅니다.

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

이 사람들은 부끄러움이 많지만 동시에 공익을 추구하는 착한 사람들이라서, 위 조건을 만족하는 자리들 중에서 결과적으로 가장 많은 사람이 앉을 수 있는 자리를 고릅니다.

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

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

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

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