Problem Description

Xiao Lan has a circular candy carousel. There are $N$ candies placed on the carousel in clockwise order. The color of the $i$-th candy is represented by a lowercase English letter $S_i$.

Xiao Lan wants to choose a cut between two adjacent candies, cut the circular carousel open, and unfold it into a line. After unfolding, the order of the candies remains the original clockwise order. There are $N$ possible cuts: you can cut between the $i$-th and the $(i + 1)$-th candies where $1 \le i < N$, or between the $N$-th and the $1$-st candies.

If, in the unfolded line of candies, every pair of adjacent candies has different colors, then this cut is called a beautiful cut.

Please calculate the number of beautiful cuts.

Input Format

The first line contains an integer $N$, indicating the number of candies.

The second line contains a string $S$ of length $N$, where the $i$-th character $S_i$ represents the color of the $i$-th candy.

Output Format

Output one line containing an integer, indicating the number of beautiful cuts.

6
ababab

6

5
aabcd

1

8
aaabbcde

0

Hint

Sample Explanation 1

On the ring, every pair of adjacent candies has different colors. No matter which cut you choose, in the unfolded line the adjacent colors are still all different, so all 6 cuts are beautiful.

Sample Explanation 2

On the ring, only the 1st and the 2nd candies have the same color. Only by cutting between these two candies will this pair of adjacent same-color candies not be kept after unfolding, so the number of beautiful cuts is 1.

Sample Explanation 3

On the ring, there are at least two pairs of adjacent candies with the same color. A single cut can break at most one adjacent relationship, so after unfolding there will still be adjacent same-color candies, and there are no beautiful cuts.

Constraints and Notes

For $30\%$ of the testdata, $2 \le N \le 200$.

For $60\%$ of the testdata, $2 \le N \le 5000$.

For all testdata, $2 \le N \le 2 \times 10^5$, and $S$ consists only of lowercase English letters.

Translated by ChatGPT 5