3.3 Bob, Alice and Alternate Strings

Score: 100pts

Time Limit: 1.00 sec

Bob was in love with Alice and wanted to impress her. Alice liked solving problems and gave Bob a problem to solve. Bob was given a string of length \(n\) consisting of 3 letters 'a', 'b', and 'c'. \(n\) is always a multiple of 3. Now, Bob was told to make the minimum number of changes in the string to make it alternate with a length of 3.

An alternate string is a string which consists of an equal number of a's, b's and c's and the difference between two consecutive occurrences of the same letter in the string is exactly 2.

Examples of alternate strings are : abcabc, bcabca, cabcabcab.

Examples of strings that are not alternate are : abacbc, cbacbc, ccc.

Alice considers this a hard problem and will be impressed if Bob solves it. But Bob, unlike Alice, is not good at solving problems and so comes to you for help. You have to help Bob to solve this problem.

An alternate string is a string which consists of an equal number of a's, b's and c's and the difference between two consecutive occurrences of the same letter in the string is exactly 2.

Examples of alternate strings are : abcabc, bcabca, cabcabcab.

Examples of strings that are not alternate are : abacbc, cbacbc, ccc.

Alice considers this a hard problem and will be impressed if Bob solves it. But Bob, unlike Alice, is not good at solving problems and so comes to you for help. You have to help Bob to solve this problem.

Constraints

\(3 \leq n \leq 9500\)

Input Format

Input Format:

The first line contains \(n\) which denotes the length of the string.

The next line contains the string made up of the characters “a”, “b” and “c”.

The first line contains \(n\) which denotes the length of the string.

The next line contains the string made up of the characters “a”, “b” and “c”.

Output Format

For each test case, print the minimum number of changes done to the string to make it alternate with a length of 3.

Example 1

Input:

6

aacabb

Output:

2

Explanation:

If we change the 2nd char to “b” and the last char to “c” we get the string “abcabc” which is alternating.

6

aacabb

Output:

2

Explanation:

If we change the 2nd char to “b” and the last char to “c” we get the string “abcabc” which is alternating.

Example 2

Input:

6

bbbccb

Output:

3

Explanation:

We can change the 1st, 2nd, 4th chars to “a”, “c”, “a”, we get the string “acbacb” which is alternating.

6

bbbccb

Output:

3

Explanation:

We can change the 1st, 2nd, 4th chars to “a”, “c”, “a”, we get the string “acbacb” which is alternating.