Có quả bóng bay, mỗi quả có một trong số màu xếp thành một cột. Ở mỗi bước được phép chọc thủng dãy bóng cùng màu từ quả trở lên. Nếu dãy bị chọc thủng có quả thì điểm số nhận được ở bước đi đó là . Các quả bóng ở trên sẽ rơi xuống lấp chổ trống trong cột.
Ví d:ụ cột ban đầu có bóng, tính từ trên xuống cột có cấu hình . Để chọc thủng hết dãy bóng, ta có thể chọc quả liên tiếp . Khi đó, điểm số nhận được sẽ là. Có cách khác để nhận được tổng điểm số cao hơn là với tổng điểm .
Yêu cầu: Cho xâu độ dài chỉ chứa các ký tự trong tập xác định màu các quả bóng tính từ trên xuống dưới. Hãy xác định tổng điểm số lớn nhất nhận được khi phá hết bóng trong cột. Nếu không thể phá hết bóng thì tổng điểm là .
Dữ liệu vào:
Dòng đầu tiên ghi số nguyên dương là số lượng test;
dòng tiếp, mỗi dòng ghi một xâu .
Dữ liệu ra:
Ghi ra kết quả mỗi test trên một dòng dưới dạng số nguyên theo thứ tự nhập.
