Author: | А. Жихарева | Time limit: | 1 sec | |
Input file: | Standard input | Memory limit: | 512 Mb | |
Output file: | Standard output |
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).
First line of input contains string S.
Second line of input contains string T.
Output must contain a single integer — the number of pairs.
1 ≤ |S|, |T| ≤ 104
No. | Standard input | Standard output |
---|---|---|
1 |
|
|
2 |
|
|