Building a KOREA String

Interview

Time limit1sMemory limit1024 MB

Summary

Given a string of the letters K, O, R, E, A, find the length of the longest subsequence that spells KOREA repeatedly, starting with K.

Level: Easy3 of 10
Topics: String, Dynamic programming
Solved: No attempts yet

Problem

The English name of Korea University is KOREA UNIVERSITY.

You are given a string $S$ consisting only of the uppercase letters K, O, R, E, and A. By deleting zero or more characters from $S$ , you want to build a string that starts with K and repeats the letters K, O, R, E, A in that order, such as "KOREAKOREAKOR". Call such a string a KOREA string.

Given the string, find the length of the longest KOREA string that you can build by deleting zero or more characters.

Input

The first line contains the string $S$ . $S$ consists only of the uppercase letters K, O, R, E, and A, and its length is between $10$ and $1\,000$ , inclusive.

Output

On the first line, print the length of the longest KOREA string that you can build.

Examples3

Example 1
Input
```
KEKRORKAKROEKREORKA
```
Expected output
```
5
```
Example 2
Input
```
OOOOOOOREA
```
Expected output
```
0
```
Example 3
Input
```
KEROKRKKAKAOA
```
Expected output
```
3
```