题目描述

对于所有正整数 $x$，定义函数 $f(x)$ 如下：

• 如果 $x$ 包含任何不是 $0$ 或 $1$ 的数字，则将 $x$ 的每一位数字，若为奇数则设为 $1$，否则设为 $0$，并返回得到的 $x$。
• 否则，返回 $x-1$。

给定一个 $x$（$1 \leq x < 10^{2\cdot 10^5}$），求需要将 $f$ 应用于 $x$ 多少次，直到 $x$ 变为 $0$。由于这个次数可能非常大，输出其对 $10^9+7$ 取模的余数。

输入格式

第一行包含 $T$（$1\le T\le 10^5$），表示独立测试用例的数量。

接下来的 $T$ 行，每行包含一个正整数 $x$，仅由数字 0-9 组成，且没有前导零。

保证所有输入整数的总位数不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含该次数对 $10^9+7$ 取模的余数。

2
24680
210

1
4

1
1234567890123456789012345678901234567890

511620083

提示

样例 1 解释

第一个测试：$x$ 经过一次操作后变为 $0$。

第二个测试：$f(x)=10$，$f^2(x)=9$，$f^3(x)=1$，$f^4(x)=0$。

评分标准

• 输入 3-5：$T\le 2000$，$x<10^{9}$
• 输入 6-7：$x<10^{18}$
• 输入 8-9：$x<10^{60}$
• 输入 10-12：无额外限制。

题目来源：Aiden Bai

翻译由 DeepSeek 完成