Ta gọi số nguyên dương K là một số BDN nếu các chữ số trong K chỉ bao gồm các 0 hoặc 1 có nghĩa. Ví dụ số K = 1, 10, 101. Cho số tự nhiên N (N<=2^63). Hãy cho biết có bao nhiêu số BDN nhỏ hơn N. Ví dụ N=100 ta có 3 số BDN bao gồm các số: 1, 10, 11.

Định dạng đầu vào: Dòng đầu tiên ghi lại số tự nhiên T là số lượng Test; T dòng kế tiếp mỗi dòng ghi lại một bộ Test. Mỗi test là một số tự nhiên N.

Ràng buộc: 1<=T<=100; 1<=N<=2^63

Đưa ra kết quả mỗi test theo từng dòng.

Input:

12
27655
16862
30017
12246
26510
6386
3668
6127
27269
24195
20859
5416

Output:

31
31
31
31
31
15
15
15
31
31
31
15