You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

Fern是一个初出茅庐的魔法使，她最近在向Frieren学习调配魔法药水。然而，魔法药水的配方出现了问题，但是Frieren还没有起床！她需要你的帮助！

Description

药水需要按照特定的顺序添加三种材料：A（火元素）、B（水元素）和C（风元素）。为了让药水稳定，必须确保在调配过程中，任意连续的3种材料中，A、B、C三种元素至少各出现一次（即不能缺少任意一种）。给定一个长度为n的材料序列（由A、B、C组成），请计算最小需要替换的材料数量，使整个序列满足上述条件。替换时，可以将任意一个材料改为A、B或C中的任意一种。

Format

Input

第一行一个整数$T(1 \leq T \leq 100)$，表示测试用例数量。 每个测试用例：

第一行一个整数 $n(3 \leq n \leq 1 \times 10^5)$，表示序列长度。

第二行一个长度为$n$的字符串$S$，由A、B、C组成。

Output

对于每个测试用例，输出一行一个整数，表示最小替换次数。

Samples

3
5
CBBCB
5
ABCAB
3
AAA

1
0
2

Note

1、CBBCB：将第三位替换为A即可满足条件，任意连续的三位都包含A、B、C：{CBA}{BAC}{ACB}。
2、ABCAB：整个序列的任意连续3个都包含A、B、C，替换0次。
3、AAA：连续3个AAA缺少B和C，需要替换至少2次（如变为ABC）。

Limitation

Time Limit: 2 second

Memory Limit: 256MiB