Minimum Operations to Make Good

You are given a string s. A string is considered "good" if it does not contain the substring abc. You can perform an operation to remove a disjoint occurrence of the substring abc from the string. In each operation, if the substring abc appears, you remove it and the remaining parts are concatenated together. However, note that in this problem, instead of actually modifying the string, you only need to count the number of disjoint occurrences of the substring abc from left to right. This count is equal to the minimum number of operations needed to make the string good.

Note that: Once an occurrence abc is removed, the search continues after that segment, thereby ensuring that overlapping occurrences are not counted.

For example:

• For s = "ababc", there is one occurrence of abc (starting at index 2), so the answer is 1.
• For s = "abcabc", there are two disjoint occurrences of abc, so the answer is 2.
• For s = "aabbcc", there is no occurrence of abc, so the answer is 0.
• For s = "zzzabczzz", there is one occurrence of abc and the answer is 1.

Your task is to process multiple test cases. For each test case, compute and output the minimum number of operations needed to make the given string good.

The operation count is computed by scanning the string from left to right and counting each non-overlapping occurrence of abc.

inputFormat

The first line of input contains an integer t — the number of test cases. Each of the following t lines contains a non-empty string s comprised of lowercase English letters.

Input format:

 t
 s1
 s2
 ...
 st

outputFormat

For each test case, output a single integer on a new line: the minimum number of operations required to make the string good.

Output format:

 result1
 result2
 ...
 resultt

## sample

4
ababc
abcabc
aabbcc
zzzabczzz

1
2
0
1

</p>