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 độ da 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 từ file văn bản ADN.INP 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)~.

Kết quả

Ghi ra file văn bản ADN.OUT một số nguyên là độ đa dạng nhỏ nhất tìm được.

Ràng buộc

• Có ~20\%~ số test ứng với ~20\%~ số điểm thỏa mãn: ~N \le 10~.

• ~20\%~ số test khác ứng với ~20\%~ số điểm thỏa mãn: ~N \le 20~.

• ~24\%~ số test khác ứng với ~24\%~ số điểm thỏa mãn: ~N \le 5000~.

• ~16\%~ số test khác ứng với ~16\%~ số điểm thỏa mãn: ~N \le 10^5~.

• ~20\%~ số test còn lại ứng với ~20\%~ số điểm thỏa mãn: ~N \le 10^6~.

Ví dụ

Input

A?T?G

Output

7

Giải thích

ATTTG là một chuỗi ADN có độ đa dạng ít nhất sau khi đã thay thế mỗi kí tự ~?~ bởi một trong bốn kí tự bốn kí tự ~A~, ~T~, ~G~, ~X~. Các đoạn con phức tạp bao gồm: ~[1, 2]~, ~[1, 3]~, ~[1, 4]~, ~[1, 5]~, ~[2, 5]~, ~[3, 5]~, ~[4, 5]~.