Ducks

A duck quacks with the sound "quack". A valid duck sound is "quack" written one or more times in a row, so "quack", "quackquack" and "quackquackquackquack" are all valid duck sounds.

Yeongseon has some ducks in her room, but she was so busy solving problems that she forgot how many there are. At some point every duck started quacking at once and the sounds got mixed together. She recorded the noise and now wants to work out how many ducks are in the room by listening to the recording.

The recording is given as a string. Each character is one sound made by one duck. The characters made by a single duck do not have to be next to each other in the recording, but reading only that duck's characters in order must give a valid duck sound. For example, "quqacukqauackck" can be explained by two ducks.

Given the recording, write a program that finds the smallest number of ducks that can be in Yeongseon's room.

The first line contains the recording. Its length is at least 5 and at most 2500, and it consists only of the five characters 'q', 'u', 'a', 'c' and 'k'.

Print the smallest number of ducks that can be in Yeongseon's room. If the recording cannot be split into valid duck sounds, print -1.

For the recording "quqaquuacakcqckkuaquckqauckack", three ducks are enough, for example like this.

Recording: quqaquuacakcqckkuaquckqauckack
Duck 1:    ____q_u__a___ck_______________
Duck 2:    __q__u_ac_k_q___ua__ckq_u__ack
Duck 3:    qu_a_______c___k__qu___a_ck___