Liên Hiệp Bò của Farmer John (UCFJ) đang tham gia giải vô địch hoofball hàng năm! Đội UCFJ gồm \(N\) bò (\(1 \le N \le 7500\)) đã giành được huy chương vàng trong môn hoofball, vượt qua đội của Farmer Nhoj một cách sát sao.

Các con bò đã sắp xếp hàng để chuẩn bị cho buổi lễ trao giải. Chúng muốn John chụp \(\frac{N(N+1)}{2}\) bức ảnh nhóm, một bức cho mỗi chuỗi con liên tiếp trong đội hình.

Tuy nhiên, John, với tư cách là huấn luyện viên của đội, rất kén chọn về cách mà các con bò nên được xếp hàng. Cụ thể, ông từ chối chụp ảnh cho một chuỗi con trừ khi nó tạo thành một palindrome, có nghĩa là giống bò của con bò thứ \(i\) từ đầu chuỗi con phải giống với giống bò của con bò thứ \(i\) từ cuối chuỗi con đối với tất cả các số nguyên dương \(i\) nhỏ hơn hoặc bằng độ dài của chuỗi con. Mỗi giống bò có thể là Guernsey hoặc Holstein.

Đối với mỗi một trong \(\frac{N(N+1)}{2}\) chuỗi con liên tiếp của đội hình, hãy đếm số lần hoán đổi tối thiểu cần thiết để sắp xếp chuỗi con đó thành một palindrome (hoặc \(-1\) nếu không thể làm được). Một lần hoán đổi đơn giản là việc lấy hai con bò kề nhau trong chuỗi con và hoán đổi vị trí của chúng. Xuất ra tổng số lần hoán đổi của tất cả các chuỗi con này.

Lưu ý rằng số lần hoán đổi cần thiết được tính độc lập cho mỗi chuỗi con (các con bò quay trở lại vị trí ban đầu giữa các bức ảnh).

Input

• Đội hình, được biểu diễn bằng một chuỗi gồm các ký tự G và H có độ dài \(N\).

Output

• Tổng số lần hoán đổi được đề cập trên đối với tất cả \(\frac{N(N+1)}{2}\) chuỗi con liên tiếp của đội hình.

Scoring

• Subtask 1: \(N \in [100, 200, 500, 1000, 2000, 5000, 5000, 5000, 5000, 5000, 7500, 7500, 7500, 7500, 7500]\).

Example

GHHGGHHGH

12