给定一个由小写拉丁字母组成的字符串。我们定义一个子串的“出现价值”为该子串在原字符串中出现的次数乘以该子串的长度。对于给定的字符串，请找出所有回文子串中最大的出现价值。

输入格式

输入仅一行，包含一个非空字符串，由小写拉丁字母（a-z）组成。

输出格式

输出一个整数，表示回文子串的最大出现价值。

样例

样例输入 1

abacaba

样例输出 1

7

样例输入 2

www

样例输出 2

4

说明

$|s|$ 表示字符串 $s$ 的长度。

字符串 $s_1s_2 \dots s_{|s|}$ 的子串是指任意非空字符串 $s_i s_{i+1} \dots s_j$，其中 $1 \le i \le j \le |s|$。任何字符串也是其自身的子串。

如果一个字符串从左向右读和从右向左读完全相同，则称其为回文串。

在第一个样例中，共有七个回文子串：$a, b, c, aba, aca, bacab, abacaba$。

• $a$ 在给定字符串中出现了 4 次，其出现价值为 $4 \times 1 = 4$
• $b$ 在给定字符串中出现了 2 次，其出现价值为 $2 \times 1 = 2$
• $c$ 在给定字符串中出现了 1 次，其出现价值为 $1 \times 1 = 1$
• $aba$ 在给定字符串中出现了 2 次，其出现价值为 $2 \times 3 = 6$
• $aca$ 在给定字符串中出现了 1 次，其出现价值为 $1 \times 3 = 3$
• $bacab$ 在给定字符串中出现了 1 次，其出现价值为 $1 \times 5 = 5$
• $abacaba$ 在给定字符串中出现了 1 次，其出现价值为 $1 \times 7 = 7$

因此，回文子串的最大出现价值为 7。

子任务

你的程序将针对以下 5 组输入数据进行测试：

子任务 1（8 分）

$1 \le |s| \le 100$。

子任务 2（15 分）

$1 \le |s| \le 1000$。

子任务 3（24 分）

$1 \le |s| \le 10000$。

子任务 4（26 分）

$1 \le |s| \le 100000$。

子任务 5（27 分）

$1 \le |s| \le 300000$。