Xâu đẹp

Một xâu đẹp là xâu có độ dài không nhỏ hơn \(2\) và kí tự đầu tiên bằng kí tự cuối cùng.
Một xâu con là dãy các kí tự liên tiếp của xâu ban đầu.

Cho trước xâu \(S\) chỉ gồm các chữ cái latin thường. Hãy đếm số lượng xâu con của \(S\) là xâu đẹp.
Nếu không có xâu con nào là xâu đẹp thì in ra \(0\).

Input

• Dòng đầu chứa số nguyên \(n\) là độ dài của xâu \(S\) \((2 \le n \le 10^5)\).
• Dòng thứ hai chứa xâu \(S\) gồm đúng \(n\) kí tự, chỉ gồm các chữ cái latin thường.

Output

• In ra một số nguyên là số lượng xâu con đẹp trong \(S\).

Input

%
9
czazbcxdx

Output

%
3

Notes

Trong ví dụ có \(3\) xâu con đẹp: czazbc, zaz, xdx.

Scoring

• (75%) \(2 \le n \le 10^3\);
• (25%) \(10^4 < n \le 10^5\).