Bajtek is learning to add numbers using the column addition method. He has placed three numbers of the same length $n$ one below the other. He is now wondering for how many pairs $(i, j)$, where $1 \le i \le j \le n$, the fragments of these numbers from the $i$-th to the $j$-th digit form a correct sum (i.e., the considered fragment of the third number is the sum of the fragments of the first and second numbers). Leading zeros are allowed in all numbers.

Input

The input consists of three lines, each containing one integer (which may potentially start with zeros). Each of these three numbers consists of the same number of digits $n$ ($1 \le n \le 10^6$).

Output

Output a single integer representing the number of pairs $(i, j)$ for which the fragment from column $i$ to column $j$ constitutes a correct addition.

Examples

Input 1

037523
040834
978367

Output 1

4

Note

Explanation of the example: Correct sums are obtained for the pairs $(2, 2)$ (because $3+4 = 7$), $(2, 4)$ (because $375+408 = 783$), $(3, 4)$ (because $75 + 8 = 83$), and $(6, 6)$ (because $3 + 4 = 7$). Note that the fragments for pairs $(2, 2)$ and $(6, 6)$ are the same, yet we count them twice. We do not count sums of fragments that are not aligned directly below each other, such as $3 + 3 = 6$.