该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题目描述】

现在小A拿到了一个仅由小写英文字母构成的字符串 $s$ 和一个仅有小写英文字母构成的字符串 $t$。
小A获得了一种魔法能力，每次可以从字符串 $s$ 中任何一个位置取出一个字符。
由于小A非常喜欢字符串 $t$，所以他现在想拥有很多字符串 $t$。
小A可以使用无限次魔法能力，现在问你他最多能利用字符串 $s$ 拼凑出多少个字符串 $t$。

【输入格式】

从文件magic.in中读取数据。

• 第一行一个字符串 $s$。
• 第二行一个字符串 $t$。

【输出格式】

输出到文件magic.out中。

• 一行一个数，表示答案。

【输入样例 1】

abcabcd
abd

【输出样例 1】

1

【输入样例 2】

ababccd
ab

【输出样例 2】

2

【输入输出样例 3】

见 magic3.in 与 magic3.ans

【数据范围与约定】

假设字符串 $s$ 的长度为 $n$，字符串 $t$ 的长度为 $m$。

• 对于测试点 $1\sim 4$：$1\le n \le 20,1\le m\le 5$。
• 对于测试点 $5\sim 6$：$1\le n \le 10^6,1\le m \le 10^6$，字符串 $s$ 中的所有字符都一样，字符串 $t$ 中的所有字符都一样。
• 对于测试点 $7\sim 12$：$1\le n \le 10^6,1\le m \le 10^6$，字符串 $s+t$ 的不同种类的字符总共最多为 $2$ 种（其中 $+$ 表示字符串拼接）。
• 对于测试点 $13\sim 20$：$1\le n \le 10^6,1\le m \le 10^6$。