Problem Description

Given a string $ S $ of length $ N $ and a string $ T $ of length $ 3 $, you can perform the following operation repeatedly:

• Choose a contiguous substring of $ S $ of length 3 that matches $ T $ and erase it (after erasing, the remaining characters are concatenated).

What is the maximum number of times you can perform this operation?

Input Format

The input is given from the standard input in the following format:

$ N $ $ S $ $ T $

Output Format

Output the maximum number of operations.

Sample Input and Output

Sample Input #1

7
adbabcd
abc

Sample Output #1

1

Sample Input #2

6
ababaa
aba

Sample Output #2

2

Sample Input #3

6
zzzzzz
abc

Sample Output #3

0

Notes/Hints

Constraints

• $1 \le N \le 100$
• $ S $ is a string of length $ N $ consisting of lowercase English letters.
• $ T $ is a string of length 3 consisting of lowercase English letters.

Sample Explanation 1

The substring from the 4th to the 6th character of $ S $ matches $ T $, so it can be erased. No further operations can be performed, so the answer is $ 1 $.

Sample Explanation 2

First, the substring from the 3rd to the 5th character of $ S $ matches $ T $, so it can be erased. $ S $ becomes aba, which matches $ T $ entirely, allowing another operation. Therefore, the answer is $ 2 $.

Sample Explanation 3

It is possible that no operations can be performed at all.

见题面 Input 部分

见题面 Output 部分