Chuỗi ADN

Tiến sĩ Tuấn là một nhà sinh học phân tử có rất nhiều công trình nghiên cứu về sự đa dạng của các chuỗi ADN. Chuỗi ADN là một dãy các nuclêôtít được biểu diễn bằng một xâu kí tự chỉ chứa bốn loại kí tự $A$, $T$, $G$, $X$ tương ứng với bốn loại nuclêôtít khác nhau. Ông đang nghiên cứu một chuỗi ADN được biểu diễn bởi một xâu $N$ phần tử $S_1{S}_2\dots S_N$. Một đoạn con $[i,j]$ được xác định bởi vị trí phần tử bắt đầu $i$ và vị trí phần tử kết thúc $j$ $(1\le i\le j\le N)$ trong xâu là một dãy gồm các phần tử liên tiếp nhau $S_i{S}_{i+1}\dots S_j$.

Tiến sĩ Tuấn định nghĩa một đoạn con là phức tạp nếu như đoạn đó chứa ít nhất hai kí tự khác nhau. Ví dụ, $[1,3]$ là một đoạn con phức tạp trong xâu $ATTTG$. Tiếp theo, ông định nghĩa độ đa dạng của một chuỗi ADN là số lượng đoạn con phức tạp trong xâu tương ứng. Hai đoạn con gọi là khác nhau nếu có ít nhất một trong hai vị trí bắt đầu và kết thúc của chúng là khác nhau.

Do sơ suất, tiến sĩ Tuấn làm mất thông tin một số phần tử trong chuỗi ADN đang nghiên cứu. Vì vậy, ông biểu diễn một kí tự chấm hỏi ($?$) cho mỗi phần tử bị mất thông tin.

Yêu cầu: Hãy giúp tiến sĩ Tuấn tính độ đa dạng nhỏ nhất của chuỗi ADN nêu trên khi thay mỗi kí tự chấm hỏi ($?$) bởi một trong bốn kí tự $A$, $T$, $G$, $X$.

Dữ liệu vào

Dữ liệu vào gồm một dòng duy nhất chỉ chứa $N$ kí tự thuộc tập $\{A,T,G,X,?\}$ viết liên tiếp nhau không có dấu cách $(1\le N\le {10}^6)$.

Dữ liệu ra

In ra một số nguyên là độ đa dạng nhỏ nhất tìm được.

Ràng buộc

• $1\le N\le {10}^6$.
• Xâu chỉ gồm các kí tự thuộc tập $\{A,T,G,X,?\}$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $N\le 10$.
• Subtask 2 ($20\%$ số điểm): $N\le 20$.
• Subtask 3 ($24\%$ số điểm): $N\le 5000$.
• Subtask 4 ($16\%$ số điểm): $N\le {10}^5$.
• Subtask 5 ($20\%$ số điểm): $N\le {10}^6$.

Ví dụ