又是一年一度的 GXCPC 大赛，今年赛会上的布置任务交给了歪歪小朋友。
为了让现场看起来氛围满满，主办方委托歪歪小朋友要给他们的会场多插一点 的旗帜。做一条 的旗帜需要用到 这五个字母，并让它们按顺序拼接起来。
为了完成这个任务，歪歪从外面采购到了一整条长度为 的布料、一把剪刀和一瓶无限量胶水。
布料是长度为 的字符串，仅有 这四种字母构成；剪刀可以用来把布料从任意处剪开，但只能裁剪两个字母中间的位置，不能从字母当中处剪开，即 可以剪开为 ；胶水可以用来把两块分离的布料进行重新拼接，一定是头尾相连的拼接，可以把要拼接布料的前后顺序互换，但不能对任意一块布料进行旋转、翻转之后再进行拼接，即 可以拼接得到 或者 。
为了满足主办方需求，歪歪需要知道她最多能利用这个布料拼接出几条 的旗帜？

第一行一个整数  ，表示数据组数。
对于每组数据，第一行一个整数   ，表示歪歪从外采购回来的一整块布料的长度。
第二行一个长度为  的字符串  ，表示歪歪从外采购回来的一整块布料。
数据保证字符串  仅由  这四种字母构成。

对于每组数据，输出一行一个整数，即歪歪最多能利用这个布料拼接出  的旗帜数。

2
10
GXCPCXCPCG
15
GGXXCCPPCCCGPCX

2
3