Cho một xâu chỉ gồm chữ cái Latin thường. Với mỗi xâu con, định nghĩa giá trị xuất hiện là số lần xâu con đó xuất hiện trong xâu ban đầu nhân với độ dài của nó.

Hãy tìm giá trị xuất hiện lớn nhất trong số các xâu con đối xứng.

Một xâu con của \(s=s_1s_2\ldots s_{|s|}\) là xâu không rỗng \(s_is_{i+1}\ldots s_j\) với \(1\le i\le j\le|s|\). Các lần xuất hiện có thể chồng lấn. Xâu đối xứng là xâu đọc từ trái sang phải giống đọc từ phải sang trái.

Dữ liệu vào

Dòng duy nhất chứa một xâu không rỗng gồm các chữ cái từ a đến z.

Dữ liệu ra

In giá trị xuất hiện lớn nhất của một xâu con đối xứng.

Ví dụ

abacaba

7

www

4

Giải thích

Trong ví dụ thứ nhất, các xâu con đối xứng khác nhau là a, b, c, aba, aca, bacab, abacaba. Giá trị xuất hiện tương ứng là \(4,2,1,6,3,5,7\), nên đáp án là \(7\).

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2014, bài Palindromes.