装备增幅¶
- 参考时间限制：1.0 秒。
- 实际时限：标准程序在目标环境的最慢用例中位耗时乘以 2，再按 0.5 秒向上取整。
- 内存限制：128 MB。
- 参考评测环境与测量
背景故事¶
装备增幅可能成功，也可能使装备降级。铁匠正在研究一种按数字判定成功的规则，希望统计不同数值范围内成功的次数。
形式化问题描述¶
把非负整数 \(S\) 分别写成二进制和十进制。两种表示都从最低位开始编号为 \(0,1,\ldots\) ，在高位补无限多个零。设对应数字为 \(b_i\) 和 \(d_i\) .
当且仅当每个位置都满足 \(b_i\ge d_i\) 时，称 \(S\) 为成功值。例如，十进制 \(10\) 的二进制为 \(1010\) ，它是成功值；十进制 \(1010\) 的二进制为 \(1111110010\) ，位置 \(3\) 上的二进制数字小于十进制数字，因此它不是成功值。
给定 \(q\) 次询问，每次给出非负整数 \(N\) ，求 \(0\le S\le N\) 中成功值的个数。数字 \(0\) 也按上述规则计算。
输入格式¶
第一行一个整数 \(q\) .接下来 \(q\) 行，每行一个十进制整数 \(N\) 。
输出格式¶
输出 \(q\) 行，每行一个整数，表示对应询问的答案。
样例 1¶
输入¶
2
55
6
输出¶
4
2
样例 2¶
输入¶
4
0
1
10
1010
输出¶
1
2
3
10
样例 3¶
输入¶
3
999999999999999999999999999999
111111111111111111111111111111
0
输出¶
715704
715704
1
样例解释¶
样例一中，不超过 \(55\) 的成功值为 \(0,1,10,11\) ；不超过 \(6\) 的成功值为 \(0,1\) .
数据范围与保证¶
\(1\le q\le100\) ；\(0\le N\le10^{30}-1\) .提交代码长度限制为 50 KB。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |