Người ta mô hình hoá một mạch điện một chiều theo cách đệ quy như sau:

• Một mạch điện có một đầu vào \(I\) và một đầu ra \(O\) với một dây dẫn nối từ \(I\) tới \(O\) được ký hiệu bằng một ký tự g.
• Nếu \(G_1\) là mạch điện có đầu vào \(I_1\) và đầu ra \(O_1\), \(G_2\) là mạch điện có đầu vào \(I_2\) và đầu ra \(O_2\) thì mạch điện nhận được bằng cách chập đầu ra \(O_1\) và đầu vào \(I_2\) thành một điểm sẽ trở thành mạch điện nối tiếp có đầu vào \(I_1\) và đầu ra \(O_2\), ký hiệu bằng xâu ký tự \(SG_1G_2\).
• Nếu \(G_1\) là mạch điện có đầu vào \(I_1\) và đầu ra \(O_1\), \(G_2\) là mạch điện có đầu vào \(I_2\) và đầu ra \(O_2\) thì mạch điện nhận được bằng cách chập hai đầu vào \(I_1, I_2\) thành một đầu vào (ký hiệu \(I_{12}\)) và chập hai đầu ra \(O_1, O_2\) thành một đầu ra (ký hiệu \(O_{12}\)) sẽ trở thành mạch điện song song có đầu vào \(I_{12}\) và đầu ra \(O_{12}\), ký hiệu \(PG_1G_2\).

Một tập các điểm được gọi là tập độc lập nếu nó không chứa hai điểm nào có dây dẫn trực tiếp. Hãy xác định số lượng điểm trong tập độc lập lớn nhất của một mạng điện cho bởi xâu ký tự gồm các chữ cái P, S, g theo quy tắc trên.

Input

• Một dòng duy nhất chứa xâu ký tự mô tả đồ thị.

Output

• Ghi ra một số nguyên duy nhất là số lượng điểm trong tập độc lập lớn nhất.

Constraints

• Xâu ký tự có độ dài không quá \(10^6\).

Example

SPSgggPgg

2

Scoring

• Bài tập không chia subtask cụ thể, giới hạn thời gian và bộ nhớ phù hợp với độ dài xâu \(10^6\).