如果一个字符串 $s$ 由数字 0 到 9 组成，我们称这个字符串为“数字串”。显然，除了以 0 开头的子串外，$s$ 的每个子串都可以看作一个正整数。设 $S$ 是包含所有这些正整数的集合，定义函数：
$$f(s) = \min\{x \mid x \in \mathbb{Z}^+, x \notin S\}$$
也就是说，$f(s)$ 是不在 $S$ 中的最小正整数。例如，$f(\text{"1241"}) = 3$，$f(\text{"542"}) = 1$，$f(\text{"11023456879"}) = 12$，以及 $f(\text{"00000"}) = 1$（注意在这种情况下，$S$ 是一个空集）。
给定一个数字串 $s$，设 $\text{substr}(i, j)$ 为 $s$ 中从第 $i$ 个数字开始到第 $j$ 个数字结束的子串，你的任务是计算：
$$\sum_{i=1}^{|s|} \sum_{j=i}^{|s|} f(\text{substr}(i, j))$$
输入格式
输入包含多组测试数据。输入的第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：
第一行也是唯一的一行包含一个数字串 $s$（$1 \le |s| \le 5 \times 10^5$）。
保证所有测试数据的 $|s|$ 之和不超过 $5 \times 10^6$。
输出格式
对于每组测试数据，输出一行包含一个整数，表示答案。
样例
输入样例 1
4 1241 542 11023456879 00000
输出样例 1
21 6 162 15
说明
下面解释第一组样例测试数据。
| 子串 | 值 | 子串 | 值 |
|---|---|---|---|
| 1 | 2 | 24 | 1 |
| 2 | 1 | 41 | 2 |
| 4 | 1 | 124 | 3 |
| 1 | 2 | 241 | 3 |
| 12 | 3 | 1241 | 3 |
因此答案为 $2 + 1 + 1 + 2 + 3 + 1 + 2 + 3 + 3 + 3 = 21$。
对于第二组样例测试数据，显然所有子串的值都为 1。因此答案为 6。