题目描述

你有一块花布条，上面有一些图案。另外还有一块可以直接使用的小饰条，上面也有一些图案。现在你需要计算一下，从这块花布条中最多可以剪出多少块完全匹配小饰条的图案。

输入格式

输入包含多组数据，每组数据占一行，由空格分隔的两个字符串组成，分别表示花布条和小饰条的图案。
当读取到单独的 # 字符时，输入结束。

花布条和小饰条均由可见 ASCII 字符组成，长度均不超过 $1000$ 个字符。

输出格式

对于每组数据，输出一行一个整数，表示能够从花布条中剪出的最多小饰条的数量。

abcde a3
aaaaaa aa
#

0
3

提示

• 在第一组数据中，花布条为 abcde，小饰条为 a3。由于花布条中没有与小饰条完全匹配的部分，因此输出为 $0$。
• 在第二组数据中，花布条为 aaaaaa，小饰条为 aa。可以在花布条中找到三个不重叠的 aa，因此输出为 $3$。