# 简单分析

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

实验室要估算快速幂程序调用乘法模块的次数。指数可能很长，研究员只提供它的二进制表示，请帮助完成这项统计。

(本故事由GPT-6重写)

## 形式化问题描述

分析下面的完整伪代码。所有变量表示任意精度整数，`multiply(x,y,m)` 返回 $xy\bmod m$ .只统计 `multiply` 的调用次数，不统计它内部的基本运算。

初始指数为非负整数 $e$ ，执行前 `index = e` .辅助参数满足：`modulus` 是质数，`base` 与 `modulus` 互质，并且 $0\le e<\text{modulus}-1$ .

```text
result = 1
index = index mod (modulus - 1)
while index > 0:
    if index mod 2 == 1:
        result = multiply(result, base, modulus)
    index = floor(index / 2)
    if index > 0:
        base = multiply(base, base, modulus)
return result
```

每个输入字符串表示一个初始指数。辅助参数不作为输入；在上述保证下，调用次数仅由指数决定。前导零不改变指数。注意右移后指数为零时，不再执行一次平方。

## 输入格式

第一行一个非负整数 $Q$ ，表示查询数。接下来 $Q$ 行，每行一个非空字符串，仅由 `0` 和 `1` 组成，表示无符号二进制整数。

## 输出格式

输出 $Q$ 行，每行一个整数，表示对应指数导致的 `multiply` 调用次数。$Q=0$ 时输出为空。

## 样例

### 样例 1

### 输入

```text
5
0
10011
1111
1
1100
```

### 输出

```text
0
7
7
1
5
```

### 样例 2

### 输入

```text
4
0000
0001
00100
00101
```

### 输出

```text
0
1
3
4
```

### 样例 3

### 输入

```text
3
10
100000
111111
```

### 输出

```text
2
6
11
```

## 样例解释

第一组中，`10011` 的数值为 $19$ .循环处理的指数依次为 $19,9,4,2,1$ ，条件乘法调用三次，平方调用四次，共七次。`0` 不进入循环；`1` 只进行一次条件乘法。第二组说明前导零不增加调用次数。

## 数据范围与保证

所有数据满足：$0\le Q\le2.1\times10^6$ ，每个字符串非空，所有字符串的长度之和不超过 $2.1\times10^6$ .每个指数均满足形式化描述中的辅助参数保证。

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