Momo 有一个字符串 $s$。每天结束时，他会将初始字符串拼接在当前字符串的末尾。也就是说，如果初始字符串是 "abc"，那么在第一天该字符串保持为 "abc"，在第二天该字符串变为 "abcabc"，在第三天变为 "abcabcabc"，依此类推。

Bobo 有另一个字符串 $t$。Bobo 很好奇他的字符串 $t$ 是否可以作为子序列在 Momo 的字符串中找到。他想知道该性质首次成立的是第几天。

如果字符串 $a$ 可以通过从字符串 $b$ 中删除若干个（可能是零个或全部）字符而获得，则称字符串 $a$ 是字符串 $b$ 的子序列。

输入格式

输入的第一行包含 Momo 的字符串 $s$。

输入的第二行包含 Bobo 的字符串 $t$。

两个字符串的长度均在 $1$ 到 $5 \cdot 10^5$ 之间（包含边界），且仅包含英文小写字母。

输出格式

输出一个整数——Bobo 的字符串首次成为 Momo 的字符串的子序列的天数。

保证对于本题的所有测试数据，这样的天数一定存在。

样例

输入样例 1

dwalkcake
cakewalk

输出样例 1

2

说明

在第一天，字符串为 "dwalkcake"，它不包含 "cakewalk" 作为子序列。

在第二天，字符串为 "dwalkcakedwalkcake"，它包含 "cakewalk" 作为子序列。