Xâu ký tự ~S = s_1 s_2 \dots s_n~ được gọi là xâu ký tự gấp đôi khi và chỉ khi ~n~ là một số nguyên chẵn, đồng thời ~s_i = s_{i + \frac{n}{2}}~ với mọi ~1 \le i \le \frac{n}{2}~. Ví dụ, baba, bonbon là các xâu ký tự gấp đôi, còn abba hay bonba thì không.

Xâu ký tự ~B = b_1 b_2 \dots b_n~ được gọi là chuỗi con của xâu ký tự ~A = a_1 a_2 \dots a_m~ khi và chỉ khi tồn tại dãy chỉ số ~i_1, i_2, \dots, i_n~ sao cho ~1 \le i_1 < i_2 < \dots < i_n \le m~ và ~b_j = a_{i_j}~ với mọi ~1 \le j \le n~. Ví dụ, tuananhcute có các chuỗi con là tuananh, cute và tuananhcute; nhưng không có các chuỗi con xautrai, kocute hay giabaoga.

Xâu ký tự ~S~ được gọi là xâu ký tự không thể gấp đôi khi và chỉ khi mọi chuỗi con của ~S~ đều không phải là xâu ký tự gấp đôi. Ví dụ, anhcute là xâu ký tự không thể gấp đôi; nhưng bingbong không phải xâu ký tự không thể gấp đôi, vì xâu có chuỗi con bngbng là xâu ký tự gấp đôi.

Cho xâu ký tự ~C = c_1 c_2 \dots c_n~, hãy đếm số cặp chỉ số ~(l, r)~ sao cho ~1 \le l \le r \le n~ và ~c_l c_{l+1} \dots c_r~ là xâu ký tự không thể gấp đôi.

Dữ liệu vào

Gồm một dòng duy nhất chứa xâu ký tự $C$. Xâu này chỉ chứa các chữ cái in thường và có độ dài từ $1$ đến $6 \cdot 10^6$.

Dữ liệu ra

Gồm một số nguyên là kết quả bài toán.

Ví dụ

Đầu vào 1

tuananhbui

Đầu ra 1

32

Đầu vào 2

anhtuanbui

Đầu ra 2

40

Tính điểm

• Subtask ~1~ ~(14\%~ số điểm~)~: Độ dài xâu ~C~ không vượt quá ~10~.
• Subtask ~2~ ~(26\%~ số điểm~)~: Độ dài xâu ~C~ không vượt quá ~100~.
• Subtask ~3~ ~(22\%~ số điểm~)~: Độ dài xâu ~C~ không vượt quá ~1000~.
• Subtask ~4~ ~(38\%~ số điểm~)~: Không có ràng buộc gì thêm.