RGBRED - Color Play

no tags 

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


hide comments
sriram_21: 2019-11-19 15:16:37

+1

huynhtuan71ti: 2019-09-16 15:10:10

nice problem !!!

ort: 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

mino_duytung: 2019-08-20 11:41:07

Hey Underwear and Caoquangphat, help me please!!!

quangphat18ti: 2019-08-20 11:15:26

so easy. 1 time for accept!!!

underwear: 2019-08-20 11:15:16

help me i cant ac


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