Xâu ký tự ~S = s1 s2 \dots sn~ đượ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 ~si = 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 = b1 b2 \dots bn~ được gọi là chuỗi con của xâu ký tự ~A = a1 a2 \dots am~ khi và chỉ khi tồn tại dãy chỉ số ~i1, i2, \dots, in~ sao cho ~1 \le i1 < i2 < \dots < in \le m~ và ~bj = 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 = c1 c2 \dots cn~, hãy đếm số cặp chỉ số ~(l, r)~ sao cho ~1 \le l \le r \le n~ và ~cl 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·{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.