Re-verse

Interview

Time limit1sMemory limit512 MB

Summary

Given a song string of length N, find the maximum number of start seconds from 0 to N-1 where the song can be sung so that overlapping shouted letters agree.

Level: Medium5 of 10
Topics: String matching, Math
Solved: No attempts yet

문제

What is the maximum number of times Siyi can start singing?

Siyi spends time peacefully doing competitive programming and decides to sing a round song. The song Siyi wants to sing is a string of $N$ uppercase English letters.

From second $0$ until any time Siyi wants, she shouts one letter every second. The time spent shouting a letter can be ignored. If the string made by joining the $N$ letters Siyi shouted from second $i$ up to just before second $i+N$ matches the song, Siyi has started singing at second $i$ .

Siyi starts singing at second $0$ , and can start singing again at every second from $1$ up to just before second $N$ .

What is the maximum number of times Siyi can start singing?

Input

The first line gives $N$ , the length of the string that represents the song Siyi wants to sing.

The second line gives the string that represents the song.

Output

Print the maximum number of times Siyi can start singing on the first line.

Constraints

$1 \le N \le 100$
The song contains only uppercase English letters.

Examples1

Example 1
Input
```
5
AABBA
```
Expected output
```
2
```