编程题
Knuth-Morris-Pratt Algorithm(KMP算法)
## 来源
The 17th Zhejiang University Programming Contest (ZOJ3957)
## 题目描述
编程实现：在给定的字符串S中查找字符串"cat"和"dog"出现的总次数。
## 输入描述
有多个测试数据。第一行为整数T（1≤T≤30），代表测试数据个数。每个测试数据占一行，为一个字符串S，1≤|S|≤1000。
## 输出描述
对每个测试数据，输出一行，为一个整数，表示在S中"cat"和"dog"出现的总次数。
## 样例输入
```txt
2
catcatcatdogggy
docadosfascat
```
## 样例输出
```txt
4
1
```