小w的进制转换
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

小w在将一个10进制数转换为二进制数的时候，不小心将“0”和“1”搞混了，也就是说本来该输出1的时候他输出了0，本来该输出0的时候他又输出了1。而他在输出答案的时候，又将输出的左右顺序搞混了。举个例子：小w将6转换为二进制，本来6的二进制表示为110，但是小w转换成了001，输出时又倒了过来变成100。现在假设评测姬中的评测数据是1,2,3,4,5,6...n也就是从1到n，问小w能AC其中的多少组测试案例？

输入描述:

第一行为一个整数T，表示有T组数据
接下来T行，每行一个整数n，表示评测姬中的数据是从1到n

输出描述:

对于每个n，输出一行一个整数表示小w能通过的案例组数。
示例1

输入

复制 
3
1
2
10

输出

复制 
0
1
2

说明

1在二进制下表示为1，而小w转换成了0，WA
2在二进制下表示为10，小w转换成了01，输出时倒置变成10，AC
10在二进制下表示为1010，小w转换成了0101，输出时倒置变成了1010，AC

备注:

对于所有数据：1\leq T\leq 10^5,1\leq n\leq10^{18}