Polycarp and the Language of Gods

2000ms

262144K

Description:

Polycarp has just finished writing down the lecture on elvish languages. The language this week was "VwV" (pronounced as "uwu"). The writing system of this language consists of only two lowercase Latin letters: 'v' and 'w'.

Unfortunately, Polycarp has written all the lecture in cursive and without any spaces, so the notes look like a neverending sequence of squiggles. To be exact, Polycarp can't tell 'w' apart from 'vv' in his notes as both of them consist of the same two squiggles.

Luckily, his brother Monocarp has better writing habits, so Polycarp managed to take his notes and now wants to make his own notes more readable. To do that he can follow the notes of Monocarp and underline some letters in his own notes in such a way that there is no more ambiguity. If he underlines a 'v', then it can't be mistaken for a part of some 'w', and if the underlines a 'w', then it can't be mistaken for two adjacent letters 'v'.

What is the minimum number of letters Polycarp should underline to make his notes unambiguous?

Input:

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of testcases.

Each of the next $$$t$$$ lines contains a non-empty string in VwV language, which consists only of lowercase Latin letters 'v' and 'w'. The length of the string does not exceed $$$100$$$.

Output:

For each testcase print a single integer: the minimum number of letters Polycarp should underline so that there is no ambiguity in his notes.

Sample Input:

5
vv
v
w
vwv
vwvvwv

Sample Output:

Note:

In the first testcase it's enough to underline any of the two letters 'v'.

In the second testcase the letter 'v' is not ambiguous by itself already, so you don't have to underline anything.

In the third testcase you have to underline 'w', so that you don't mix it up with two letters 'v'.

In the fourth testcase you can underline 'w' to avoid all the ambiguity.

In the fifth testcase you can underline both letters 'w' and any of the two letters 'v' between them.

Informação

Provedor Codeforces

Código CF1431B