Bậc đối xứng

Xâu $s$ độ dài $n$ được gọi là $k$-đối xứng nếu $s$ là một xâu đối xứng (palindrome) và đồng thời tiền tố cùng hậu tố độ dài $\lfloor n/2\rfloor$ của $s$ đều là xâu $(k-1)$-đối xứng. Theo định nghĩa, mọi xâu (kể cả xâu rỗng) đều là $0$-đối xứng.

Bậc đối xứng của xâu $s$ là số $k$ lớn nhất sao cho $s$ là $k$-đối xứng. Ví dụ, xâu abaaba có bậc đối xứng bằng $3$.

Cho một xâu $s$. Hãy tính tổng bậc đối xứng của tất cả các tiền tố của $s$.

Dữ liệu vào

Một dòng duy nhất chứa xâu $s$ khác rỗng, gồm các chữ cái Latin (phân biệt chữ hoa và chữ thường) và chữ số.

Dữ liệu ra

In ra một số duy nhất, là tổng bậc đối xứng của tất cả các tiền tố của $s$.

Ràng buộc

• $1\le |s|\le {10}^6$
• $s$ chỉ gồm các ký tự trong tập a-z, A-Z, 0-9

Ví dụ