# Knuth-Morris-Pratt Algorithm

Time Limit: 1 Second

Memory Limit: 65536 KB

## Description

In computer science, the Knuth-Morris-Pratt string searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.

Edward is a fan of mathematics. He just learnt the Knuth-Morris-Pratt algorithm and decides to give the following problem a try:

Find the total number of occurrence of the strings "cat" and "dog" in a given string s.

As Edward is not familiar with the KMP algorithm, he turns to you for help. Can you help Edward to solve this problem?

## Input

There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 30), indicating the number of test cases. For each test case:

The first line contains a string s (1 ≤ |s| ≤ 1000).

## Output

For each case, you should output one integer, indicating the total number of occurrence of "cat" and "dog" in the string.

## Sample Input

7
catcatcatdogggy
dogdddcat
catcatcatcatccat
dogdogdogddddooog
dcoagtcat
doogdog


## Sample Output

4
1
2
5
3
1
1


## Hint

For the first test case, there are 3 "cat" and 1 "dog" in the string, so the answer is 4.

For the second test case, there is only 1 "cat" and no "dog" in the string, so the answer is 1.

None