Get Time To Stabilize (Pipeline Service Outage)

Each second, based on the string at the start of that second, every failedService simultaneously deletes the character immediately to its left; the deleted character may itself be a failed service. Find the number of seconds that pass before the string stops changing.

输入格式

The first line is pipeline, and the second line is a single failedService character. Length 1..200000; this site uses lowercase letters.

输出格式

Output a single integer answer.

样例 1

输入：

database
a

输出：

2

样例 2

输入：

aaaa
a

输出：

1

样例 3

输入：

bbb
a

输出：

0

样例说明

Example 1: the three a are at indices 1, 3, 5; the leading segment has length 1 and the two gaps have length 2, so the answer is 2. Example 2: in the first second, the first three a are deleted simultaneously by their right neighbors, leaving only one, so the answer is 1. Example 3: there is no a and no deletion happens, so the answer is 0.