Kick

Time limit3sMemory limit1024 MB

Summary

Count the occurrences of the substring kick in a lowercase string of up to 5 million characters, including overlapping matches.

Level: Easy1 of 10
Topics: String, String matching
Solved: No attempts yet

Problem

You are given a string $s$ of lowercase English letters. A "kick" is a substring of $s$ that consists of the letter 'k', then 'i', then 'c', then 'k'. Count the number of distinct "kick" substrings in $s$ . Kicks may overlap.

Input

The input is a single line containing the string $s$ . The string consists of lowercase English letters, and its length is at most $5 \times 10^6$ .

Output

Print the number of "kick" substrings on a line.

Examples2

Example 1
Input
```
kickickstartkicks
```
Expected output
```
3
```
Example 2
Input
```
kickkickkickkick
```
Expected output
```
4
```