Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3957
Knuth-Morris-Pratt Algorithm

Time Limit: 1 Second      Memory Limit: 65536 KB

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
```

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

Author: WANG, Yucheng
Source: The 17th Zhejiang University Programming Contest Sponsored by TuSimple
Submit    Status