Description

Original source: HDU 2087

A piece of floral fabric contains some patterns, and there is also a small usable decorative strip with some patterns. Given the floral fabric and the decorative strip, calculate how many pieces of the decorative strip can be maximally cut from the floral fabric.

Input Format

The input consists of multiple test cases, which terminate when the # character is encountered. Each test case contains only one line, consisting of the floral fabric and the decorative strip separated by a space. Both the floral fabric and the decorative strip are represented by visible ASCII characters and will not exceed 1000 characters in length.

Note: This # should be a single character. If a string starts with #, it does not mean the input has terminated!

Output Format

For each test case, output a single integer on a line, representing the maximum number of decorative strips that can be cut from the floral fabric.

Sample 1

abcde a3
aaaaaa aa
#

0
3

Constraints and Hints

For all test cases, the length of the strings is ≤ 1000.