Giao bóng cầu lông

Bối cảnh

Bài toán được mô tả qua yêu cầu và dữ liệu dưới đây.

Yêu cầu

FullHouse Dev đang chơi cầu lông hôm nay. Luật giao bóng trong trận đấu đơn cầu lông như sau:

• Người chơi bắt đầu trận đấu sẽ giao bóng từ bên phải sân của họ.
• Bất cứ khi nào một người chơi giành được điểm, họ sẽ được giao bóng tiếp theo.
• Nếu người giao bóng đã giành được số điểm chẵn trong một ván, họ sẽ giao bóng từ bên phải sân cho điểm tiếp theo.
• FullHouse Dev sẽ là người chơi bắt đầu trận đấu.

Cho biết số điểm P mà FullHouse Dev đạt được khi kết thúc trận đấu, hãy xác định xem FullHouse Dev đã giao bóng từ bên phải sân bao nhiêu lần.

Input

• Dòng đầu tiên chứa một số nguyên T - số lượng test case.
• Mỗi test case gồm một dòng chứa số nguyên P - số điểm FullHouse Dev đạt được.

Output

• Với mỗi test case, in ra một dòng duy nhất số lần FullHouse Dev giao bóng từ bên phải sân.

Ràng buộc

• \(1 ≤ T ≤ 10^3\)
• \(0 ≤ P ≤ 10^9\)

Ví dụ 1

Input

4
2
9
53
746

Output

2
5
27
374

Giải thích ví dụ

• Test case 1: FullHouse Dev đạt được 2 điểm. Anh ấy giao bóng từ bên phải 2 lần, khi điểm số là 0 và 2.
• Test case 2: FullHouse Dev đạt được 9 điểm. Anh ấy giao bóng từ bên phải 5 lần, khi điểm số là 0, 2, 4, 6, 8.

Thông tin học tập

• Buổi: B04
• Concepts: multiple test cases, loops, arithmetic, conditionals
• Giới hạn kiến thức: B01-B04
• Time limit: 2 seconds
• Memory limit: 64 MB
• Point: 10