shiba quyết định chơi một trò chơi có độ khó cao. Trong trò chơi, có tất cả \(n\) cửa, cửa thứ \(i\) nếu thắng sẽ được thưởng một lượng điểm đúng bằng \(i\), ngược lại nếu thua sẽ bị trừ một lượng điểm đúng bằng \(i\). Trò chơi được thiết kế bởi _minhduc, mà cậu ấy bị ám ảnh với các số \(2\) nên các cửa là luỹ thừa của \(2\) thì sẽ được giảm độ khó.

Do kĩ năng chơi không quả hay của mình, shiba chỉ có thể thắng được các cửa được giảm độ khó. Hỏi số điểm shiba nhận được sau khi chơi đủ \(n\) trò chơi là bao nhiêu?

Input

• Dòng thứ nhất chứa một số nguyên dương \(T\) (\(T \le 10^3\)) - số lượng bộ test.
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(n\) (\(n \le 10^8\)).

Output

• Gồm \(T\) dòng, mỗi dòng là một số nguyên là kết quả của bộ test đó.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 10^3\).
• Subtask \(2\) (\(70\%\) số điểm): không có ràng buộc gì thêm.

Example

2
1
4

1
4