Byteotian Printing Factory (BPF) has received a large production order for striped wallpaper. Striped wallpaper is the hit of the season in interior design. Each wallpaper has $n$ equal-width coloured vertical stripes. BPF is to take care of the design and printing of wallpapers. The customer described the colour of certain wallpaper stripes. In the case of other stripe colours, the customer allowed BPF a complete freedom.

In the production of wallpapers BPF use matrices to print a certain number of consecutive stripes on the wallpaper. The matrix has a specific colour of each of the printed stripes. The matrix may be shorter than the entire wallpaper. If the matrix consists of $k$ stripes it is applied in all $n-k+1$ possible positions where its stripes align with the wallpaper stripes, each time printing all the matrix stripes. In this way, a single wallpaper stripe can be printed over more than once. In case a given stripe is printed over using various colours, the final colour is a blend of these colours.

BPF employees, irrespective of their sense of aesthetics, would primarily like to design the shortest possible matrix that will allow printing the entire wallpaper. They must bear in mind that in the case of stripes defined by the customer they must use pure colour, without any addition of any other colour. In other words, each matrix application printing over such a single colour stripe, the matrix stripe colour must be exactly as defined by the client.

Input

The only input line contains a string composed of Latin alphabet upper case letters and stars (*), specifying the desired appearance of the wallpaper. The letters represent different colour stripes, while the stars indicate stripes of the colour not specified by the client. The length of the character string $n$ satisfies $1 \le n \le 1\,000\,000$.

Output

Your program should output a single line containing a single integer $k$: the minimum matrix length, which would enable printing the desired wallpaper.

Examples

Input

A*B*B*A

Output

6

Explanation

The matrix of length 6 which enables printing the wallpaper presented at the input (composed of seven stripes) is ABBBBA.