Đề bài

Ở giảng đường Công nghệ thông tin, TrZit nổi tiếng với tài leo rank gánh team, và cũng khét tiếng với thói quen cắm mặt vào điện thoại dưới gầm bàn. Đúng lúc combat căng thẳng nhất trong giờ Toán rời rạc, thầy giáo bắt quả tang, thu luôn điện thoại rồi quay lên bảng viết dãy số:

$$1, 2, 3, \ldots, n$$

"Mỗi lượt, em chọn hai số a và b đứng ở hai vị trí khác nhau trên bảng, xóa cả hai số này đi rồi viết vào giá trị ~\vert{}a - b\vert{}~. Lặp lại thao tác cho đến khi trên bảng chỉ còn đúng một số duy nhất, đó chính là quân bài Joker. Tìm được cách chơi để Joker đạt giá trị lớn nhất thì em được nhận lại điện thoại và qua môn. Không thì sẽ cấm thi!!!"

Nhìn chiếc máy đang nằm trên bàn giáo viên và sợ bị cấm thi, TrZit vô cùng lo lắng, run sợ. Nhưng ngặt nỗi cả buổi lo leo rank nên cậu chẳng hiểu gì về bài toán này. Thầy giáo còn ra liên tiếp t dãy số như vậy, mỗi dãy có độ dài n khác nhau. Hãy giúp TrZit tìm giá trị lớn nhất mà quân Joker có thể đạt được ở từng dãy để chuộc lại điện thoại và không phải học lại.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương t là số lượng dãy số.
• t dòng tiếp theo, mỗi dòng chứa một số nguyên dương n, mô tả dãy ~1, 2, \ldots, n~ tương ứng.

Kết quả

In ra t dòng, dòng thứ i là giá trị lớn nhất có thể của Joker ứng với n ở dòng thứ i của dữ liệu vào.

Ràng buộc và subtask

• ~1 \le t \le 10^5~
• ~1 \le n \le 10^{18}~
• Với ~n = 1~, trên bảng đã chỉ có một số nên Joker chính là số đó.

Ví dụ

Input

2
4
3

Output

4
2

Giải thích:

• Với ~n = 4~: ~\{1,2,3,4\} \to \{1,1,4\} \to \{0,4\} \to \{4\}~.
• Với ~n = 3~: ~\{1,2,3\} \to \{1,3\} \to \{2\}~.