Next: Line Interval Density Up: UMD HPC98 Questions Previous: UMD HPC98 Questions

Maximum Repeating Substring

You must find a substring of an input string, such that the substring consecutively repeats the most number of times.

A string s is said to be a substring of string t if the characters of s appear consecutively in order within t. For example, ``BAT'' is a substring of ``ACROBATS'' since these characters occur in the same order as follows ``ACROBATS''.

A substring repeats consecutively if it appears multiple times in a string, with no gaps between its occurrences. For example, the string ``BLAAABADBADX" has two repeating substrings: 'A', which repeats three times, and 'BAD', which repeats twice. The answer reported is '3', since the length of the repeating substring is not considered. Only consecutive repetitions of a substring are counted, so the last two occurrences of 'A' don't count toward the total number of repetitions.

Input format

The input will be a single line of text containing the input string. Assume the longest string will be 50 characters.

Output format

Output ``Maximum repeat: " and the maximum number of times a substring is consecutively repeated.

Examples

Input:

blaaabadbadx

Output:

Maximum repeat: 3

Input:

ababcdcdcdcdef

Output:

Maximum repeat: 4

Test data used in judging

Input 1	Output 1
Input 2	Output 2
Input 3	Output 3
Input 4	Output 4

Our solution