N. Two-Sided RPS
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The judging team lines up $$$n$$$ contestants, each showing Rock (R), Paper (P), or Scissors (S). Choose a divider between two adjacent contestants.

On the left, the leftmost contestant starts as champion and duels the others one by one from left to right toward the divider. On the right, the rightmost contestant starts as champion and duels the others one by one from right to left toward the divider. The two group champions then duel.

Rock beats Scissors, Scissors beats Paper, and Paper beats Rock. Equal gestures keep that same gesture as champion. Count the dividers for which the final champion shows the requested gesture.

Input

The first line contains an integer $$$n$$$ ($$$2 \le n \le 2 \times 10^5$$$).

The second line contains a string $$$s$$$ of length $$$n$$$ over R, P, and S, in line order.

The third line contains one character $$$t$$$ (R, P, or S) — the requested gesture.

Output

Print the number of valid divider positions.

Example
Input
3
RPS
R
Output
1
Note

For the divider after the first contestant, the right group is won by Scissors, then Rock wins the final duel. For the other divider, Scissors wins the final duel. Therefore exactly one divider produces Rock.