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 ≤ 10⁵

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