Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4095
Strange Function

Time Limit: 8 Seconds      Memory Limit: 262144 KB

If a string $s$ is composed of digits from 0 to 9, we call this string a "digit string". It's obvious that each substring of $s$, except those who start with 0, can be considered as a positive integer. Let $\mathbb{S}$ be the set containing all these positive integers, define a function $$f(s) = \min\{x | x \in \mathbb{Z}^+, x \not\in \mathbb{S}\}$$

That is to say, $f(s)$ is the smallest positive integer which is not in $\mathbb{S}$. For example, $f(\text{"1241"}) = 3$, $f(\text{"542"}) = 1$, $f(\text{"11023456879"}) = 12$, and $f(\text{"00000"}) = 1$ (note that in this case, $\mathbb{S}$ is an empty set).

Given a digit string $s$, let $\text{substr}(i, j)$ be the substring of $s$ which starts from the $i$-th digit and ends at the $j$-th digit, your task is to calculate $$\sum_{i=1}^{|s|}\sum_{j=i}^{|s|} f(\text{substr}(i, j))$$.

Input

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first and only line contains a digit string $s$ ($1 \le |s| \le 5 \times 10^5$).

It's guaranteed that the sum of $|s|$ of all test cases will not exceed $5 \times 10^6$.

Output

For each test case output one line containing one integer, indicating the answer.

Sample Input

4
1241
542
11023456789
00000

Sample Output

21
6
162
15

Hint

We explain the first sample test case below.

Substring Value Substring Value
1 2 24 1
2 1 41 2
1 2 241 3
12 3 1241 3

So the answer is 2 + 1 + 1 + 2 + 3 + 1 + 2 + 3 + 3 + 3 = 21.

For the second sample test case, it's obvious that the values of all the substrings are 1. So the answer is 6.


Author: WENG, Caizhi
Source: The 19th Zhejiang University Programming Contest Sponsored by TuSimple
Submit    Status