Cho một xâu \(S\) chỉ chứa toàn các kí tự thường và kí tự \(*\). Bạn hãy tìm xem nếu thay thế hết các kí tự \(*\) bởi một kí tự thường thì xâu kết quả có thể chia thành tối thiểu bao nhiêu dãy xâu đồng kí tự.

Ví dụ: Xâu \(aaaabbbcaaac\) có thể chia thành \(5\) dãy xâu đồng kí tự là \(aaaa, bbb, c, aaa, c\).

Đầu vào

Một xâu chỉ chứa kí tự thường có độ dài không quá \(10^6\).

Đầu ra

Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ

Đầu vào:

ab*b**c

Đầu ra:

3

Giải thích: Lần lượt điền kí tự \(b, c, c\) vào vị trí \(*\) ta thu được xâu \(abbbccc\) có thể chia thành tối thiểu \(3\) dãy xâu đồng kí tự.