After hearing the devastating news that the beloved sculptures of Rundle Mall were stolen, Tom wanted to give the people of Adelaide something special upon his return.

This gift would be a tower, meticulously crafted to fit the specifications that he has laid out. For ease of construction and transportation, this tower will be split into modules. These modules must be arranged and stacked in the correct order, otherwise it's not a valid Tower of Tom's!

Each module is denoted by a single character, and the rules for arranging them are as follows:

• o (sphere, required): A sphere module to commemorate the Mall's Balls. Must have at least one in the tower.
• b (bird, required): Must have at least one bird module in the tower. Must at least have a sphere module below and above it anywhere within the tower.
• T (Tom's special, required): Tom's special module that must be placed every ~3~ modules. That is, for a given module at index ~i~ (~1~-indexed), place one when ~i \equiv 0 \pmod{3}~.
• H (hat, optional): A bucket hat that must always be placed at the top of the tower, if it exists.

Tom tries to get some of his friends back home in Adelaide to construct it for him before he returns, but none of them can seem to get it right! Given a series of towers that they have constructed, can you fix them such that they're correct Tower of Tom's?

Input

Each test contains multiple test cases. The first line contains an integer ~t~ ~(1 \leq t \leq 10^5)~, the number of test cases. The descriptions of the test cases follows.

Each test case contains an integer ~h~ ~(4 \leq h \leq 1000)~, the height of the tower; and a string ~T~, the tower itself. The tower is laid on its side, with the start of the string representing the top of the tower.

Output

For each test case, output the minimum number of module replacements required to make the tower valid. It is guaranteed that you are able to make a valid tower.

Clarifications

• T modules need to be on indexes ~i \equiv 0 \pmod{3}~, they can't be anywhere else.
• H modules don't need to exist, and can be removed when replacing modules.
• b modules don't need to be directly surrounded by o modules, as long as there is one earlier and later than all b modules.

Example

Input 1

3
6 HoHbbH
6 ooTooT
10 obTbbTbbTo

Output 1

3
1
0

For the first test case, we can look at replacing modules at index ~i~ (~1~-indexed), where ~i \equiv 0 \pmod{3}~ with the T modules. Then, we ensure that hat module (H) is that the top, and that the bird modules (b) have at least one sphere module o below and above it within the tower.

A minimum of three replacements is required to get a valid tower:

HoTboT

For the second test case, the tower follows all of the rules, apart from the fact that there is a bird module missing. We can replace either the ~2~nd or the ~4~th o module with a b module to get a valid tower:

obTooT
ooTboT

For the third test case, all rules are met, making this a valid Tower of Tom's.