# 装备增幅

- 参考时间限制：1.0 秒。
- 实际时限：标准程序在目标环境的最慢用例中位耗时乘以 2，再按 0.5 秒向上取整。
- 内存限制：128 MB。
- [参考评测环境与测量](../../../docs/评测环境与性能.md)

## 背景故事

装备增幅可能成功，也可能使装备降级。铁匠正在研究一种按数字判定成功的规则，希望统计不同数值范围内成功的次数。

## 形式化问题描述

把非负整数 $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

### 输入

```text
2
55
6
```

### 输出

```text
4
2
```

## 样例 2

### 输入

```text
4
0
1
10
1010
```

### 输出

```text
1
2
3
10
```

## 样例 3

### 输入

```text
3
999999999999999999999999999999
111111111111111111111111111111
0
```

### 输出

```text
715704
715704
1
```

## 样例解释

样例一中，不超过 $55$ 的成功值为 $0,1,10,11$ ；不超过 $6$ 的成功值为 $0,1$ .

## 数据范围与保证

$1\le q\le100$ ；$0\le N\le10^{30}-1$ .提交代码长度限制为 50 KB。

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |