Một xâu có độ dài lớn hơn ~1~ chỉ gồm các chữ cái la tinh in thường được gọi là đối xứng, nếu ta đọc xâu đó từ trái sang phải và từ phải sang trái là như nhau. Một xâu được gọi là siêu đối xứng, nếu nó là xâu đối xứng hoặc được tạo thành bằng cách ghép liên tiếp từ nhiều xâu đối xứng.

Yêu cầu: Cho một xâu ~S~, hãy đếm số xâu con siêu đối xứng của ~S~. (Xâu con của một xâu ~S~ là một đoạn liên tiếp các ký tự của ~S~).

Input

Chứa xâu ~S~ với độ dài không vượt quá ~1000~.

Output

Ghi ra số xâu con tìm được.

Sample Input

abc

Sample Output

0