Given an integer, **S** represented as a string, get the **sum of all possible substrings of this string**.

**Input:**

A string **S** that representing the number.

**Output:**

Print sum of all possible substrings as required result.

**Constraints:**

1 <= T <= 100
1 <= S <= 1012

**Example:**

Input:
1234
326
Output:
1670
395

**Explanation:**

For the first input 1234,
All possible substrings are
1, 2, 3, 4, 12, 13, 23, 34, 123, 234, 1234
Total sum = 1 + 2 + 3 + 4 + 12 + 23 + 34 + 123 + 234 + 1234 = 1670
For the second input 326
All possible substrings are
3, 2, 6
32, 26
326
Total sum=3+2+6+32+26+326= 395

The solution approach is by storing the substring sums to compute the exact next substring sum

All the statements are self-explanatory except the one which is the fundamental idea of the entire storing process. That is the below one,

Let's check this with an example,

Let's start for the same example

N=4 here

So, we need to fill up a 4X4 DP table,

After filling the base case,

Now, I am computing for len=2

Start=0, end=1

Start=1, end=2

Start=2, end=3

For len =3

Start=0, end=2

Start=1, end=3

Len=4

Start=0, end=3

At each step we have summed up, so result is stored at sum.

C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: