You are a treasure hunter traveling around the world. Finally, you’ve got an ancient text indicating the place where the treasure was hidden. The ancient text looks like a meaningless string of characters at first glance. Actually, the secret place is embedded as the longest repeated subsequence of the text. Well, then, what is the longest repeated subsequence of a string? First, you split the given string \textbf{S} into two parts \textbf{F }and \textbf{R}. Then, you take the longest common subsequence \textbf{L} of \textbf{F} and \textbf{R} (longest string \textbf{L} that is a subsequence of both \textbf{F} and \textbf{R}). Since there are many possible ways to split \textbf{S} into two parts, there are many possible \textbf{L}’s. The longest repeated subsequence is the longest one among them. For example, the longest repeated subsequence of "\textbf{ABCABCABAB}" is "\textbf{ABAB}", which is obtained when you split "\textbf{ABCABCABAB}" into "\textbf{ABCABC}" and "\textbf{ABAB}". Now your task is clear. Please find the longest repeated subsequence and get the hidden treasure! \InputFile The input consists of multiple data sets. Each data set comes with a single line that contains one string of up to \textbf{300}capital letters. It is guaranteed that there is at least one repeated subsequence in each string. The end of input is indicated by a line that contains "\textbf{#END}". This line should not be processed. \OutputFile For each data set, print the longest repeated subsequence on a line. If there are multiple longest subsequence, print any one of them.