Description

一卷桌布，里面包含一些图案，小明家里有一块桌布，上面也包含一些图案。

对于给定的一卷桌布，小明想要计算一下能从这卷桌布里剪出多少块和自己家那块完全相同的桌布。

Input Format

输入数据为多组数据，读取到 # 字符时结束。

每组数据仅有一行，包含两个以空格分开的字符串，表示一卷桌布和小明家里的桌布图案。这些图案都是用 ASCII 字符表示的，不会超过 1000 个字符。

注意：这个 # 应为单个字符。若某字符串开头有 #，不意味着读入结束！

Output Format

对于每组数据，输出一行一个整数，表示能从一卷桌布中剪出的桌布数量。

abcde a3
aaaaaa aa
#​

0
3​

Hint

对于全部数据，字符串长度 ≤1000

Source

kmp