Description

The definition of folding is as follows:

1. A string can be considered its own folding. Denoted as S = S.

2. X(S) is the folding of the string formed by concatenating $X$ copies of S. Denoted as X(S) = SSSS…S.

3. If A = A', B = B', then AB = A'B'. For example: since 3(A) = AAA, 2(B) = BB, we have 3(A)C2(B) = AAACBB, and 2(3(A)C)2(B) = AAACAAACBB.

Given a string, find its shortest folding.

For example, the shortest folding of AAAAAAAAAABABABCCD is 9(A)3(AB)CCD.

Input Format

A single line containing the string S, whose length does not exceed $100$.

Output Format

A single line containing the length of the shortest folding.

NEERCYESYESYESNEERCYESYESYES

14

Hint

One shortest folding is 2(NEERC3(YES)).

It is guaranteed that for $100 \%$ of the testdata, the string S consists only of uppercase letters.

Translated by ChatGPT 5