Unique subsequences
/

## Algorithms, Arrays, String Manipulation, String manipulation

Problem
Editorial
Analytics

You are given a string $S$ that contains $N$ characters. Your task is to determine the maximum possible size of the subsequence $T$ of $S$ such that no two adjacent characters in $T$ are the same.

Note: The string contains only lowercase English alphabets.

Input format

• First line: A single integer $T$ denoting the number of test cases
• For each test case:
• First line: Single integer $N$ denoting the size of the string
• Second line: $S$ denoting the string

Output format

For each test case, print a single line containing one integer that represents the maximum size of the subsequence that satisfies the provided condition.

Constraints

$1 \le T \le 10^3\\ 1 \le N \le 10^5$

Note: The sum of $N$ overall test cases do not exceed $10^6$.

SAMPLE INPUT
2
5
ababa
5
aaaac


SAMPLE OUTPUT
5
2


Explanation

For the string $ababa$ we can select the complete string as $T$, since no two adjacent characters are identical, so answer is $5$.

For the string $aaaac$ the maximum possible $T$ which can be formed is $ac$ so answer is 2.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...