Hệ nhị phân là một hệ đếm, dùng hai ký tự để biểu đạt một số. Hai ký tự đó là \(0\) và \(1\). Một số nguyên được gọi là Yero binary number nếu như biểu diễn nhị phân của nó chỉ chứa một số \(0\). Ví dụ, \(11\) là một Yero binary number, còn \(4\) và \(7\) thì không phải. Bạn được
cho một số nguyên dương \(N\), hãy đếm xem trong khoảng từ \(1...N\) có bao nhiêu Yero binary number.

Input

• Dòng thứ nhất chứa số \(T(1 \leq T \leq 100)\) - Thể hiện số lượng test case.
• \(T\) dòng tiếp theo, mỗi dòng chứa số nguyên \(n (1 \leq n \leq 10 ^ {18})\).

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm.

Example

2
5
11

2
4