Có n quả bóng bay, mỗi quả có một trong số 4 màu {R, B, G, Y } 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 liên tiếp nhau từ 2 quả trở lên. Nếu dãy bị chọc thủng có k quả thì điểm số nhận được ở bước đi đó là k^2. Các quả bóng ở trên sẽ rơi xuống lấp chỗ trống trong cột sao cho thứ tự trên dưới ban đầu của các quả bóng không bị thay đổi.

Ví dụ, cột ban đầu có 10 bóng, tính từ trên xuống cột có cấu hình BBGGBBY Y Y . Để chọc thủng hết dãy bóng, ta có thể chọc các quả liên tiếp BB, GG, BB, Y Y Y . Khi đó, điểm số nhận được sẽ là 2^2 + 2^2 + 2^2 + 3^2 = 21. Tuy nhiên, ta có cách khác để nhận được tổng điểm số cao hơn là GG, BBBB, Y Y Y , với tổng điểm là 2^2 + 4^2 + 3^2 = 29.

Yêu cầu: Cho xâu S độ dài n chỉ chứa các ký tự trong tập {R, B, G, Y } biểu diễn 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à 0.

Dữ liệu vào

Dòng đầu tiên ghi một số nguyên dương T ≤ 5 là số lượng test.

Mỗi dòng trong số T dòng tiếp theo chứa một xâu S.

Kết quả

Mỗi dòng ghi ra một số nguyên là kết quả tìm được tương ứng với test trong dữ liệu vào.

Input

4
BBGGBBYYY
BGGGB
BGGBGGGG
GBGB

output

29
13
24
0

Hạn chế

• Subtask 1 (28 điểm) n ≤ 15;
• Subtask 2 (16 điểm) n ≤ 200, chỉ có 2 màu G, B và độ dài các đoạn màu giống nhau liên tiếp là như nhau;
• Subtask 3 (56 điểm) n ≤ 200.