对于所有正整数 $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$ 行，每行包含一个仅由数字 $0-9$ 组成的正整数 $x$，且不含前导零。

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

输出格式

对于每个测试用例，在单独的一行中输出操作次数对 $10^9+7$ 取模后的结果。

样例

样例输入 1

2
24680
210

样例输出 1

1
4

说明 1

第一个测试用例：$x$ 在一次操作后变为零。

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

样例输入 2

1
1234567890123456789012345678901234567890

样例输出 2

511620083

子任务

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

题目来源：Aidan Bai