## 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.

## 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