codeforces#P1789F. Serval and Brain Power

Serval and Brain Power

Description

Serval loves Brain Power and his brain power problem.

Serval defines that a string $T$ is powerful iff $T$ can be obtained by concatenating some string $T'$ multiple times. Formally speaking, $T$ is powerful iff there exist a string $T'$ and an integer $k\geq 2$ such that $$T=\underbrace{T'+T'+\dots+T'}_{k\text{ times}}$$

For example, gogogo is powerful because it can be obtained by concatenating go three times, but power is not powerful.

Serval has a string $S$ consists of lowercase English letters. He is curious about the longest powerful subsequence of $S$, and he only needs you to find out the length of it. If all the non-empty subsequences of $S$ is not powerful, the answer is considered to be $0$.

A string $a$ is a subsequence of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) characters.

The first line contains a single string $S$ ($|S|\leq 80$) consisting of lowercase English letters.

Print a single integer — the length of the longest powerful subsequence of $S$. If all the non-empty subsequences of $S$ is not powerful, print $0$.

Input

The first line contains a single string $S$ ($|S|\leq 80$) consisting of lowercase English letters.

Output

Print a single integer — the length of the longest powerful subsequence of $S$. If all the non-empty subsequences of $S$ is not powerful, print $0$.

buaa
codeforcesround
oooooooooooaaaaeaaiaujooooooooooooo
zero
2
6
24
0

Note

For the first sample, all of the non-empty subsequences of buaa are listed below:

  • b
  • u
  • a (occurred twice, buaa and buaa)
  • bu
  • ba (occurred twice, buaa and buaa)
  • ua (occurred twice, buaa and buaa)
  • aa
  • bua (occurred twice, buaa and buaa )
  • baa
  • uaa
  • buaa

Since $\texttt{aa} = \texttt{a} + \texttt{a}$, aa is a powerful subsequence. It can be shown that aa is the only powerful subsequence among them. So the answer is $2$.

For the second sample, the longest powerful subsequence is codcod from codeforcesround. So the answer is $6$.