K. hsq 的子序列
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

hsq 现在有一个仅由字符 u, s, t 组成的字符串 ， 他正在仔细地数 ， 每次从中提取一个不相交的子序列 ， 最多能提取出多少个 usst ( 上海理工大学的英文缩写 ) 。

这个时候 zzj 来了 ， 他觉得 hsq 的这个问题太简单了 ， 于是在字符串上泼了一些墨水 。

hsq 回来可太难过了 ， 他拼尽全力 ， 发现原字符串中有些字符被墨水严重覆盖 ， 变成了一种模糊的类型 1 ：

类型 1 ， 它原本可能是 u 或者 t 。

其他没有被覆盖的字符依然清晰地显示为 u, s 或 t 。

现在你获得了这个被墨水污染的字符串 ， 请你帮助 hsq 判断出 ， 在最好的情况下 ( 即由你来决定每个 1 具体代表 u 还是 t ) ， 最多可能提取出多少个 互不相交 的 usst 子序列 。

Input

第一行包含一个整数 $$$T$$$ （ $$$1 \le T \le 10^5$$$ ） ， 表示测试数据的组数 。

对于每组测试数据 ： 第一行包含一个整数 $$$n$$$ （ $$$1 \le n \le 2 \cdot 10^5$$$ ） ， 表示字符串 $$$S$$$ 的长度 。 第二行包含一个长度为 $$$n$$$ 的字符串 $$$S$$$ ， 字符串仅由字符 u, s, t 以及 1 组成 。

数据保证所有测试数据的 $$$\sum n \le 2 \cdot 10^5$$$ 。

Output

对于每组测试数据 ， 输出一行一个整数 ， 表示在最优策略下 ， 最多能提取出的互不相交的 usst 子序列的数量 。

Example
Input
2
5
u1sst
8
ususs1st
Output
1
2
Note

对于第一组测试数据，可以将 1 替换为 u，字符串变为 ussst，此时最多可以提取出 1 个 usst 子序列（例如选择下标为 1, 3, 4, 5 的字符）。

对于第二组测试数据，可以将 1 替换为 t，字符串变为 ususstst。此时我们可以提取出 2 个 互不相交 的 usst 子序列：

第一个子序列选择下标为 1, 2, 4, 6 的字符（对应字符分别为 u, s, s, t）；

第二个子序列选择下标为 3, 5, 7, 8 的字符（对应字符分别为 u, s, s, t）。