Nauw là một người rất thích chơi game nên anh quyết định tổ chức một giải đấu LOL cho ~n~ người chơi với luật như sau:

Gọi ~a_i~ là số điểm của người ~i~ ở thời điểm lượt chơi cần xét. Ban đầu ~a_i = 0~ với mọi ~i~.

Thực hiện liên tục các lượt chơi cho đến khi trò chơi dừng lại, mỗi lượt sẽ diễn ra như sau:

• Chọn ra ~2~ đối thủ ~x~ và ~y~ để đấu với nhau, sao cho ~|a_x - a_y| \le 1~. Nếu không tồn tại ~2~ đối thủ như vậy, trò chơi sẽ được dừng lại.

• Người thua sẽ bị loại và số người chơi giảm xuống ~1~.

• Gọi người thắng là ~x~, thì tăng ~a_x~ lên ~1~: ~a_x = a_x + 1~.

Hỏi với một giải đấu gồm ~n~ người tham gia, xét mọi cách sắp xếp trận đấu có thể xảy ra, số điểm lớn nhất mà một người có thể đạt được trước khi bị loại hoặc sau khi trò chơi dừng là bao nhiêu?

Nauw có ~q~ câu hỏi như trên cần phải được trả lời. Do còn bận đi chuẩn bị cho giải đấu nên bạn hãy giúp Nauw trả lời giúp ~q~ câu hỏi đó.

Input

• Dòng đầu chứa số nguyên dương ~q~ (~1\le q \le 10^6~) thể hiện số lượng test.

• ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~ (~1\le n \le 10^{18}~).

Output

• ~q~ dòng, mỗi dòng in ra một số nguyên dương duy nhất là kết quả của test tương ứng.

Sample Input 1

2
4
7

Sample Output 1

2
3

Notes

Ở ví dụ ~1~, số điểm lớn nhất có thể đạt được là ~2~ bằng cách sau:

• Cặp (~1, 2~) đấu với nhau, người ~1~ thắng.

• Cặp (~3, 4~) đấu với nhau, người ~3~ thắng.

• Cặp (~1, 3~) đấu với nhau, người ~1~ thắng.

Ở ví dụ ~2~, số điểm lớn nhất có thể đạt được là ~3~ bằng cách sau:

• Cặp (~1, 2~) đấu với nhau, người ~1~ thắng.

• Cặp (~1, 3~) đấu với nhau, người ~1~ thắng.

• Cặp (~4, 5~) đấu với nhau, người ~4~ thắng.

• Cặp (~6, 7~) đấu với nhau, người ~6~ thắng.

• Cặp (~4, 6~) đấu với nhau, người ~4~ thắng.

• Cặp (~1, 4~) đấu với nhau, người ~1~ thắng.