Cho một chuỗi ~S~ chỉ chứa những ký tự in thường trong bảng chữ cái tiếng Anh.

Một chuỗi được gọi là chuỗi cân bằng nếu thoả mãn các tiêu chí sau:

• Độ dài chuỗi là số chẵn;

• Các ký tự phân biệt xuất hiện ở hai nửa của chuỗi là giống nhau.

Ví dụ:

• "aaazzaaz" là chuỗi cân bằng vì mỗi nửa chuỗi "aaaz" | "zaaz" chứa đúng hai ký tự phân biệt 'a' và 'z';

• "abbba" không là chuỗi cân bằng vì độ dài chuỗi là số lẻ (không chia đôi được);

• "aaab" không là chuỗi cân bằng vì nửa bên trái chỉ chứa ký tự 'a' còn nửa bên phải chứa ký tự 'a' và 'b'.

Yêu cầu: Hãy đếm số lượng chuỗi con liên tiếp của chuỗi ~S~ là chuỗi cân bằng.

Input

Một dòng duy nhất gồm chuỗi ~S~ có độ dài không vượt quá ~10^5~.

Output

Một số nguyên là kết quả của bài toán.

Scoring

Sample Input 1

aazazz

Sample Output 1

4

Sample Input 2

ababbcd

Sample Output 2

2

Notes

Trong ví dụ thứ nhất, có ~4~ chuỗi thoả mãn: "aa", "aazazz", "azaz", "zz".

Trong ví dụ thứ hai, có ~2~ chuỗi thoả mãn: "abab", "bb".