Cho một xâu $S$ chỉ chứa toàn các kí tự thường và kí tự $\ast$. Bạn hãy tìm xem nếu thay thế hết các kí tự $\ast$ 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í $\ast$ ta thu được xâu $abbbccc$ có thể chia thành tối thiểu $3$ dãy xâu đồng kí tự.