징검다리

승택이는 강을 건너려 한다. 수영을 못하기 때문에 강에 놓인 징검다리를 밟고 건너간다.

수영은 못해도 제자리뛰기는 정말 잘해서, 원하는 곳이면 어디로든 한 번에 점프해 갈 수 있다.

승택이는 지금 강의 한쪽 기슭에 서 있다. 강에는 1번, 2번, 3번, ..., $N$번 징검다리가 차례대로 놓여 있다. 출발하는 기슭을 위치 $0$, $i$번 징검다리를 위치 $i$라고 하면 한 번 점프하는 거리는 두 위치의 차이다.

강폭이 넓어서 징검다리의 수는 엄청나게 많다. 이 징검다리를 모두 밟고 싶지는 않았던 승택이는 제자리뛰기 실력을 발휘해 적절한 개수의 징검다리만 밟고 가기로 했다.

강 건너편으로 바로 점프하는 것도 가능하지만, 더 재미있게 강을 건너려고 승택이는 다음 규칙을 정했다.

1. 첫 점프로는 아무 징검다리나 밟을 수 있다. 이 점프가 첫 점프다.
2. 두 번째 점프부터는 바로 앞 점프보다 1 이상 긴 거리를 뛰어야 한다.
3. $N$번 징검다리는 반드시 밟아야 한다.
4. $N$번 징검다리에서 강 건너편으로 이동할 때는 점프가 아니므로 위 규칙이 적용되지 않는다.

승택이가 이 규칙을 지키며 강을 건널 때 밟을 수 있는 징검다리의 최대 개수를 구하라.

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

이어지는 $T$개의 줄에 각각 정수 $N$이 하나씩 주어진다. $N$은 징검다리의 총 개수다. ($1 \le N \le 10^{16}$)

각 테스트 케이스마다 승택이가 밟을 수 있는 징검다리의 최대 개수를 한 줄에 출력한다.