RGBRED - Color Play

Given a color string consisting of primary colors only (Red, Green, Blue), any two adjacent colors can be combined to form the third color. Print the smallest possible length of the color string after all possible combinations. 

Input

First line contains a positive integer T representing number of testcases.

Next line contains a number n denoting the size of color array.

Next line contains a n size color string

1 ≤ T ≤ 100

1 ≤ n ≤ 105

Output

Output minimum possible length of the final color string.

Example

Input:
2
3
RGB
4
RGBR Output:
2
1

Explanation:
Example 1:
[RG]B → BB

Example 2:
[RG]BR → B[BR] → [BG] → R


Added by:Kriti Joshi
Date:2019-07-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2019-11-19 15:16:37
+1
2019-09-16 15:10:10
nice problem !!!
2019-09-04 02:34:21
ad-hoc, very good problem Kriti Joshi, had to brute it with another program and recursion to find solution
2019-08-20 11:41:07
Hey Underwear and Caoquangphat, help me please!!!
2019-08-20 11:15:26
so easy. 1 time for accept!!!
2019-08-20 11:15:16
help me i cant ac
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.