Problem D. Digital substring ≡

Statement

Strings S and T consist of digits from 0 to 9.

Let use define transformation step for a string of digits as follows. Select any substring and replace it by the sum of all its digits, as long as that sum does not exceed 9. For example, string 1263 can be transformed into any of 363, 183, 129, 93. String 12345 can be transformed into 339 by two transformation steps.

Your program must count the number of pairs i, j such that 1 ≤ i ≤ j ≤ |T| and substring of T from i-th to j-th digit (inclusive) can be transformed into S by some number of steps (including zero).

Input format

First line of input contains string S.

Second line of input contains string T.

Output format

Output must contain a single integer — the number of pairs.

Constraints

1 ≤ |S|, |T| ≤ 10⁴

Sample tests

123
5123889

1

58
911453571

3