Xâu đẹp

Xâu đẹp là xâu có độ dài lớn hơn hoặc bằng \(2\), trong đó kí tự đầu và kí tự cuối của xâu bằng nhau. Xâu con của một xâu là dãy các kí tự liên tiếp của xâu đó.

Cho trước một xâu \(S\). Hãy đếm số lượng xâu con là xâu đẹp trong xâu \(S\). Hai xâu con ở hai vị trí khác nhau được tính là hai xâu con khác nhau, kể cả khi nội dung giống nhau. Nếu không có xâu con nào là xâu đẹp thì in ra số \(0\).

Input

• Dòng đầu tiên ghi số nguyên dương \(n\) (\(2 \le n \le 10^5\)) là độ dài của xâu \(S\).

• Dòng thứ hai ghi xâu \(S\) chỉ gồm các kí tự chữ cái latinh thường.

Ràng buộc:

• Có \(75\%\) số test ứng với \(75\%\) số điểm có \(2 \le n \le 10^3\);

• Có \(25\%\) số test ứng với \(25\%\) số điểm có \(10^4 < n \le 10^5\).

Output

Một số nguyên duy nhất là số lượng xâu đẹp trong xâu \(S\).

Example

Input:

9
czazbcxdx

Output:

3

Note

Có \(3\) xâu đẹp thỏa mãn điều kiện là: czazbc (bắt đầu và kết thúc bằng c), zaz (bắt đầu và kết thúc bằng z), xdx (bắt đầu và kết thúc bằng x). Các chữ cái a, b, d chỉ xuất hiện một lần nên không tạo được xâu đẹp.