A DNA sequence is composed of four distinct characters: `A`, `T`, `G`, and `X`. A DNA sequence is considered complicated if it contains two or more different types of characters. For instance, the sequence AAT is complicated, but GG is not. The diversity of a DNA string refers to the number of complicated substrings it contains.
Marisa has a DNA string; however, she has lost information at certain positions, represented by the character `?`. Let's assist her in filling these positions with characters `A`, `T`, `G`, and `X` to achieve a DNA string with the lowest possible diversity.
### Input
- A single line contains a string $S$, the DNA string.
### Output
- Print the smallest possible diversity of the DNA string.
### Constraints
- $1 \le |S| \le 10^5$.
### Example
Input:
```
A?T?G
```
Output:
```
7
```
**Note: One possible string to obtain a diversity of 7 is `ATTTG`.**
