Problem D. Digital substring

Author:А. Жихарева   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

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| ≤ 104

Sample tests

No. Standard input Standard output
1
123
5123889
1
2
58
911453571
3

0.067s 0.012s 13