Giao bóng cầu lông

Bối cảnh

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

Yêu cầu

• 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 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, biểu thị số lượng bộ test.
• Mỗi bộ test bao gồm một dòng chứa một số nguyên P, là số điểm mà FullHouse Dev đạt được.

Output

• Với mỗi bộ test, 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 1: FullHouse Dev đạt được 2 điểm khi kết thúc trận đấu. Điều này có nghĩa là anh ấy đã giao bóng hai lần từ bên phải sân, một lần khi điểm số của anh ấy là 0 và một lần nữa khi điểm số là 2.

• Test 2: FullHouse Dev đạt được 9 điểm khi kết thúc trận đấu. Điều này có nghĩa là anh ấy đã giao bóng 5 lần từ bên phải sân. Các điểm số khi anh ấy phải giao bóng từ bên phải là: 0, 2, 4, 6, 8.

Thông tin học tập

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