Xâu Palindrome (hay còn gọi là xâu đối xứng) là một chuỗi ký tự có tính chất: đọc từ trái sang phải và từ phải sang trái đều giống nhau. Xâu có ~1~ ký tự cũng được xem là xâu Palindrome.

Xâu con của xâu ~S~ là một dãy các ký tự liên tiếp trong xâu ~S~. Phép chia Palind trên xâu ~S~ là một cách chia xâu ~S~ thành các xâu con liên tiếp. Trong đó, từng xâu con trong cách chia đó đều là xâu Palindrome.

Yêu cầu: Cho xâu ~S~, hãy xác định số cách chia Palind có thể thực hiện trên xâu ~S~.

Input

Dòng duy nhất ghi xâu ~S~ (không rỗng) chỉ gồm các ký tự chữ cái thường 'a'..'z'. Số lượng ký tự của ~S~ không quá ~16~ ký tự.

Output

Một dòng duy nhất ghi số lượng phép chia Palind có thể thực hiện trên xâu ~S~.

Scoring

Sample Input 1

aab

Sample Output 1

2

Sample Input 2

a

Sample Output 2

1

Sample Input 3

banana

Sample Output 3

5

Notes

Ví dụ 1: ~S = \text{aab}~ có thể thực hiện được ~2~ phép chia Palind như sau: ~[aa][b]~ và ~[a][a][b]~.