Longest Good Subsequence

You are given a string s and your task is to determine the length of the longest good subsequence that can be constructed from it. A good subsequence is defined as a sequence in which no two consecutive characters are the same. Note that the characters in the subsequence must appear in the same order as they appear in the original string. For example, given the string "aabbcc", one possible good subsequence is "abc", whose length is 3.

Input Format: The first line contains an integer T, the number of test cases. Each of the following T lines contains a string s.

Output Format: For each test case, output a single line containing the length of the longest good subsequence of the given string.

Examples:

Input:
3
aabbcc
abcabc
abac
Output:
3
6
4

</p>

inputFormat

The input begins with a single integer T representing the number of test cases. Each of the next T lines contains a non-empty string s composed of lowercase English letters. It is possible that s is an empty string.

outputFormat

For each test case, print a single integer on a new line representing the length of the longest good subsequence, where a good subsequence is one that does not contain two identical consecutive characters.

## sample

3
aabbcc
abcabc
abac

3
6
4

</p>