Maximum Times Word Removed

Each time, choose any characters from s that, after rearranging, form exactly the target t, then delete those characters; all other characters remain. Find the maximum number of target words that can be taken. The characters need not form a contiguous substring, and they need not spell t in their original order.

输入格式

The two lines contain s and t. The original statement only specifies lowercase letters; on this site 1≤|s|,|t|≤200000 and the target is non-empty.

输出格式

Output a single integer, the answer.

样例 1

输入：

abacbc
bca

输出：

2

样例 2

输入：

abdadccacd
edac

输出：

0

样例 3

输入：

aaaaab
aa

输出：

2

样例说明

The answers are 2, 0 and 2 respectively. In the third example each target uses two a's, so it can be taken only twice.