Prefix Removal Game

Two players, P and B, play a game on a string \(S\) consisting of lowercase letters. Initially, the string is given as \(S_0\), and both players start with 0 points.

The players take turns, with P taking the first move. In each move, the current player chooses a non-empty prefix \(X\) of the current string \(S\). The player gains points equal to the number of occurrences of \(X\) in \(S\) (counting overlapping occurrences). After that, the prefix \(X\) is removed from \(S\). The game terminates immediately when \(S\) becomes empty.

The objective of player P is to maximize the difference between his score and player B's score, while player B aims to minimize this difference. Assuming both players play optimally, you are to determine the final score difference \(\bigl(\text{P's score} - \text{B's score}\bigr)\).

Note: For example, consider \(S_0 = \mathtt{ababa}\). One optimal sequence of moves is:

• P chooses the prefix \(a\) (which appears 3 times in \(ababa\)), scoring 3 points. The string becomes \(baba\).
• B chooses the prefix \(ba\) (which appears 2 times in \(baba\)), scoring 2 points. The string becomes \(ba\).
• P chooses \(ba\) (which appears 1 time in \(ba\)), scoring 1 point and emptying the string.

The final score difference is \(4 - 2 = 2\).

inputFormat

The input consists of a single line containing the string \(S_0\) (a non-empty string of lowercase English letters).

outputFormat

Output a single integer representing the final difference \(\text{P's score} - \text{B's score}\) if both players play optimally.

sample

ababa

2