Description

Little P and Little B like to play games, and they found skip. skip told them about the following game:

• There is a string $S$ containing lowercase letters. At the start of the game, it is a string $S_0$ given by skip. The game calculates scores for Little P and Little B, both starting at $0$.
• Little P and Little B take turns operating on this string, with Little P going first. In each turn, the current player can perform the following operation:
  • Choose a non-empty prefix of $S$ (which can be $S$ itself), gain a score equal to the number of occurrences of this prefix in $S$, and remove this prefix from $S$.
• If $S$ becomes empty after an operation, the game ends.

To help you better understand the rules, consider the following example:

• Initially, $S_0 = ababa$;
• Little P chooses the prefix $a$ of $ababa$, gains 3 points, and $S$ becomes $baba$;
• Little B chooses the prefix $ba$ of $baba$, gains 2 points, and $S$ becomes $ba$;
• Little P chooses $ba$, gains 1 point, the string becomes empty, and the game ends. Finally, Little P gains 4 points, and Little B gains 2 points.

Little P wants to maximize the difference between Little P's score and Little B's score, while Little B wants to minimize this value. They want to know what the final difference between Little P's score and Little B's score will be, assuming both players play optimally.

Input

Read from standard input.

The input consists of a single line containing a string $S_0$ composed of lowercase letters.

Output

Output to standard output.

A single integer representing the value of Little P's score minus Little B's score, assuming both players play optimally.

Examples

Example 1

Input

ababa

Output

2

Note

The optimal strategies for Little P and Little B are those given in the problem description.

Subtasks

Let $n$ be the length of the string $S$. For all test cases, $1 \le n \le 10^6$, and the string $S$ consists of lowercase letters.