Đấu trường tham lam

Hai người chơi tham gia trò chơi sau với một rương vàng ban đầu chứa $N$ đồng. Người chơi thứ nhất đi trước, sau đó hai người luân phiên nhau lượt. Trò chơi kết thúc khi rương rỗng.

Trong mỗi lượt, người chơi hiện tại phải chọn đúng một trong các nước đi sau:

1. Lấy $1$ đồng vàng từ rương.
2. Lấy đúng một nửa số đồng vàng trong rương. Nước đi này chỉ được phép khi số đồng vàng hiện có trong rương là số chẵn.

Cả hai người chơi đều chơi tối ưu nhằm tối đa hoá số đồng vàng mà bản thân thu được đến cuối ván. Hãy tính số đồng vàng mà người chơi thứ nhất nhận được khi cả hai cùng chơi tối ưu.

Dữ liệu vào

• Dòng đầu chứa số nguyên $T$ — số bộ dữ liệu.
• $T$ dòng tiếp theo, mỗi dòng chứa một số nguyên $N$ — số đồng vàng ban đầu trong rương.

Dữ liệu ra

In ra $T$ dòng, mỗi dòng là một số nguyên — số đồng vàng tối đa mà người chơi thứ nhất có thể đạt được trong bộ dữ liệu tương ứng.

Ràng buộc

• $1\le T\le {10}^5$
• $1\le N\le {10}^{18}$

Ví dụ