Longest Valid Subsequence

Given a string s consisting of uppercase English letters, your task is to find the length of the longest subsequence that can be formed from s by deleting some (possibly zero) characters, such that no two consecutive characters in the subsequence are identical.

More formally, let \( s = s_1s_2\ldots s_n \). You are to form a subsequence \( s' \) by taking \( s'_1 = s_1 \) and, for each \( i > 1 \), including \( s_i \) if and only if \( s_i \neq s_{i-1} \). The length of \( s' \) is the answer.

inputFormat

The input is given via standard input. The first line contains an integer ( T ) (( T \ge 1 )) representing the number of test cases. Each of the following ( T ) lines contains a non-empty string s consisting of uppercase letters.

outputFormat

For each test case, output a single integer on a new line representing the length of the longest subsequence where no two consecutive characters are the same.## sample

6
AACCAGT
GGGG
ACGT
AA
A
AGAGAG

5
1
4
1
1
6