Ducks

Interview

Time limit2sMemory limit512 MB

Summary

Split a string of q,u,a,c,k into the fewest interleaved subsequences, each reading as 'quack' repeated.

Level: Medium5 of 10
Topics: Greedy, Simulation, String
Solved: No attempts yet

Problem

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.

Input

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'.

Output

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.

Hint

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___

Examples6

Example 1
Input
```
quqacukqauackck
```
Expected output
```
2
```
Example 2
Input
```
kcauq
```
Expected output
```
-1
```

Example 3

Input

quackquackquackquackquackquackquackquackquackquack

Expected output

Example 4

Input

qqqqqqqqqquuuuuuuuuuaaaaaaaaaacccccccccckkkkkkkkkk

Expected output

Example 5
Input
```
quqaquuacakcqckkuaquckqauckack
```
Expected output
```
3
```
Example 6
Input
```
quackqauckquack
```
Expected output
```
-1
```