Setting

A subsequence of a given sequence \(S\) consists of \(S\) with zero or more elements deleted. Formally, a sequence \(Z = z_1, z_2, \ldots, z_k\) is a subsequence of \(X = x_1, x_2, \ldots, x_m\) if there exists a strictly increasing sequence \(< i_1, i_2, \ldots, i_k >\) of indices of \(X\) such that for all \(j = 1, 2, \ldots, k\) we have \(x_{i_j} = z_j\). For example, \(Z = bcdb\) is a subsequence of \(X = abcbdab\) with corresponding index sequence \(< 2, 3, 5, 7 >\).

Your job is to write a program that counts the number of occurrences of \(Z\) in \(X\) as a subsequence such that each has a distinct index sequence.

Input

The input consists of a number of lines, each specifying a test case. Each line consists of two strings separated by a space character. The first is string \(X\), composed entirely of lowercase alphabetic characters and having length no greater than 10,000. The second is string \(Z\) having length no greater than 100 and also composed of only lowercase alphabetic characters. Be assured that neither \(Z\) nor any prefix or suffix of \(Z\) will have more than \(10^{100}\) distinct occurrences in \(X\) as a subsequence.

An empty line terminates the input.

Output

For each test case, output the number of distinct occurrences of \(Z\) in \(X\) as a subsequence, each on a separate line.

Sample Input

babgbag bag
rabbbit rabbit

Sample Output

5
3

This is challenge 10131 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.

Statistics

Difficulty (0 votes)
Average test runtime 0.27
Points (changes over time) 10
Tried by 4 users
Solved by 3 users

Global ranking

# Name Runtime Points worth
1 贝尔恩德 0.15 16
2 Mac 0.33 7
3 Dark 0.34 7