Maximum Nesting Level of k-Quotations

In literature and programming, nested quotations allow for complex string representations. In this problem we use the notion of k-quotations defined as follows:

Definition.

• A 1-quotation is a string that begins with a single quote character (') and ends with a single quote character, and does not contain any quote characters in between. For example, 'this is a string' is a 1-quotation.
• For any integer k > 1, a k-quotation is a string that begins with k consecutive quote characters, ends with k consecutive quote characters, and whose middle part (called the inner string) contains a non-empty sequence of (k-1)-quotations. This sequence may be interleaved with any number (possibly zero) of non-quote characters. For example, ''All 'work' and no 'play'' is a 2-quotation.

Your task is: Given a string, determine its maximum possible nesting level k for which it forms a valid k-quotation. If the string does not qualify as any valid quotation according to the above definitions, output 0.

Note: When checking for a valid k-quotation for k > 1, you only need to verify that there exists at least one substring (of the inner part) that is a valid (k-1)-quotation.

The formulas in the problem statement are written in LaTeX. For example, the notion of a k-quotation is defined using the formula $k \ge 1$ and the recursive structure is shown with $k>1$ leading to (k-1)-quotations.

inputFormat

The input consists of a single line containing a string. The string is composed of ASCII characters and may include quote characters (').

outputFormat

Output a single integer – the maximum nesting level k for which the string forms a valid k-quotation, or 0 if no valid quotation structure exists.

sample

'hello'

1