오리

오리의 울음소리는 "quack"이다. 올바른 울음소리는 "quack"을 한 번 이상 연속해서 이어 붙인 것이다. 예를 들어 "quack", "quackquack", "quackquackquackquack"은 올바른 울음소리이다.

영선이의 방에는 오리가 여러 마리 있는데, 문제를 푸는 데 몰두하다가 몇 마리인지 잊어버렸다. 어느 순간 오리들이 한꺼번에 울기 시작했고, 울음소리가 서로 섞였다. 영선이는 그 소리를 녹음해 두었고, 녹음을 다시 들으면서 방에 오리가 몇 마리 있는지 알아내려고 한다.

녹음한 소리는 문자열로 나타낸다. 문자 하나는 오리 한 마리가 낸 소리 하나이다. 한 오리가 낸 문자들이 녹음에서 연속할 필요는 없지만, 그 오리가 낸 문자만 순서대로 이어 붙이면 올바른 울음소리가 되어야 한다. 예를 들어 "quqacukqauackck"은 오리 두 마리가 운 소리로 볼 수 있다.

영선이가 녹음한 소리가 주어졌을 때, 영선이 방에 있을 수 있는 오리의 최소 마리 수를 구하는 프로그램을 작성하시오.

첫째 줄에 영선이가 녹음한 소리가 주어진다. 소리의 길이는 5 이상 2500 이하이고, 소리는 'q', 'u', 'a', 'c', 'k' 다섯 가지 문자로만 이루어져 있다.

첫째 줄에 영선이 방에 있을 수 있는 오리의 최소 마리 수를 출력한다. 녹음한 소리를 오리들의 올바른 울음소리로 나눌 수 없으면 -1을 출력한다.

녹음이 "quqaquuacakcqckkuaquckqauckack"인 경우, 다음과 같이 오리 세 마리가 울었다고 볼 수 있다.

  녹음: quqaquuacakcqckkuaquckqauckack
오리 1: ____q_u__a___ck_______________
오리 2: __q__u_ac_k_q___ua__ckq_u__ack
오리 3: qu_a_______c___k__qu___a_ck___