SP10574 SCCCER - Soccer Ceremony

有四只来自巴西圣保罗的球队：科林斯、帕尔梅拉斯、桑托斯和圣保罗。为奖励在冠军赛上表现突出的球员，四支球队打算提前将他们选中，观看决赛。 今天，是决出四支球队中的冠军的重要日子。球员们赶到现场后，发现他们都只记得自己座位的行数，却不记得自己作为在哪一列。为了不违反足球史上最重要的规则之一，你要赶紧将他们安置好。 这条规则你应该知道，但为了题目的完整性，我还是要说明一下，就是同队不能有3个或3个以上的队员坐在一起。

第一行，一个整数t，表示测试数据的组数。 对于每组测试数据，一个整数n和一个长度为n的字符串s，其中n代表球员个数，s[i]代表每个球员在哪支队伍，s[i]为C,P,N,S中的一个，分别代表科林斯、帕尔梅拉斯、桑托斯和圣保罗。 每组测试数据将用一个回车分开。

输出为不违反规则而需要交换的最小次数。如果找不到解，输出-1。 ### 输入样例 2 8 CCCCCCPN 3 CCC ### 输出样例 4 -1