输入描述:

本题输入包含多组数据。
第一行一个整数 ，表示测试数据组数，对于每组数据格式如下：
    第一行一个整数 ，表示字符串的长度。
    第二行一个长度为  的字符串 ，保证输入仅含  和 。
对于单个测试文件保证所有测试数据组的  之和小于等于 。

输出描述:

输出共 行，每行一个整数，表示至少需要多少次修改才能使得字符串  中至少包含三个子串为好串。