The definition of beauty quotes sequence:

Empty string is a series of beautiful quotes.

If X is a series of beautiful quotes, then [X], (X), {X} is also a beautiful array brackets.

If X, Y ranges are 2 beautiful quotation marks, the sequence XY is also beautiful.

Example: () [() ()] is a row of beautiful quotes. {[)} Is not beautiful array brackets.

Given a string S contains only the brackets. When writing out the characters from position to position i of the string S j (1 <= i <= j <= Length (S)) we obtain the sequence S (i, j). An S (i, j) is good substring of string S if S (i, j) is a series of beautiful quotes. Request the number of good substring of S.

Input

A single line: string S.

The first 10 trials, the length of S is less than 101.

The next 10 trials, the length of S is less than 10001.

10 final test, the length of S is less than 1000001.

Output

A single integer: Number of possible substring of S.

Example

Input:
(){](({}))[]

Output:
6