I. Chef Abushogi cooking
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Chef Abushogi is making his signature turkey and cheese sandwiches. A perfect sandwich requires exactly 4 ingredients in a strict specific order: a slice of Bread, then Turkey, then Cheese, and finally another slice of Bread.

You are given a string $$$S$$$ representing the ingredients available on the kitchen counter from left to right. The string consists only of the characters:

  • 'b' representing Bread;
  • 't' representing Turkey;
  • 'c' representing Cheese;

To make a sandwich, you must select 4 characters from the string such that their indices $$$i_1 \lt i_2 \lt i_3 \lt i_4$$$ correspond exactly to the sequence "btcb". Each character in the string can be used in at most one sandwich.

Find the maximum number of perfect sandwiches Chef Abushogi can make.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the string $$$S$$$.

The second line of each test case contains the string $$$S$$$ of length $$$n$$$, consisting only of the characters 'b', 't', and 'c'.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the maximum number of perfect sandwiches that can be formed.

Example
Input
5
8
btcbbtcb
6
btctcb
7
bbttccb
4
tbcb
10
bbbtcbttcb
Output
2
1
1
0
2
Note

In the second case btctcb, we can form one sandwich using indices 1, 2, 3, 6. In the third case bbttccb, we can form one sandwich using indices 2, 3, 5, 7