Wow and Queries

Interview

Time limit1sMemory limit1024 MB

Summary

Given Q strings made of W and O, count how many times the substring WOW appears in each one.

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

Problem

Hongik University has a mascot named Wow. People who see Wow cannot help but shout because it is so cute. While studying sounds, you learned how to measure how cute Wow is.

Let the sound people make be a string $S$ . You found that the number of occurrences of the substring WOW in $S$ is exactly how cute Wow is at that moment. Given $Q$ sounds, find the cuteness of each one.

Input

The first line contains the number of sounds $Q$ . ( $1 \leq Q \leq 100$ )

From the second line on, each of the next $Q$ lines gives one sound $S$ to analyze. (The length of $S$ is at least $1$ and at most $1\,000$ , and $S$ contains only W and O.)

Output

For each sound, print the cuteness of Wow analyzed from that sound, one per line, in input order.

Examples1

Example 1
Input
```
4
WOW
WWO
WOWOWWOW
OWOOWOOW
```
Expected output
```
1
0
3
0
```