描述

定义一个奇怪的函数 f(x)（x > 0）：

• 若 x 的十进制表示中存在非 0 和非 1 的数字，则将 x 的每一位数字替换为：若该位数字为奇数则变为 1，否则（偶数）变为 0，得到新数 y（保持原位数，无前导零丢失），并令 f(x) = y；
• 否则（即 x 的每一位仅含 '0' 或 '1'），令 f(x) = x - 1。

给定正整数 x（满足 1 ≤ x < 10^(2×10⁵)，即最多 200000 位），反复应用 f 直到结果为 0。求所需应用次数（即从 x 开始，f(x), f(f(x)), ...，直到首次得到 0 的步数），答案对 10⁹+7 取模。

注意：0 不再应用 f；过程严格终止于 0，且保证有限步内可达。

输入输出格式

输入

第一行一个整数 T（测试用例数）。接下来 T 行，每行一个不含前导零的十进制字符串 x（长度 ≥ 1），表示初始数。所有输入字符串总长度不超过 10⁶。

输出

对每个测试用例，输出一行一个整数：应用 f 直到得到 0 所需的最少步数，对 10⁹+7 取模。

样例

2
24680
210

1
4

限制

• 1 ≤ T ≤ 10⁵，但所有输入数字字符串总长度 ≤ 10⁶；
• 每个 x 是合法十进制正整数字符串，无前导零，长度在 1 到 200000 之间；
• 时间限制：单次计算需高效（不能模拟每一步，因步数可能极大）；
• 空间限制：O(字符串长度)；
• 输出答案需对 10⁹+7 取模。