You're playing a game in which you're given a sequence of various jewels. If adjacent jewels are of the same type, you can gain 1 point by collecting them (thus removing them from the sequence).

Given a string of lowercase English letters, where each letters represents a different type of jewel, find the maximum score you can obtain by playing the game optimally.

For example, if = "abccbda", you can play as follows:

  1. Collect "cc". These jewels are removed, the string becomes "abbda", and your score becomes 1.
  2. Collect "bb". The string becomes "ada", and your score becomes 2.

After this, it is impossible to collect any more jewels. Therefore, the answer is 2.

Input Format

The first line contains an integer, , denoting the number of test cases.

Each test contains a single string, .

Constraints

  • length of

Output Format

Print lines. Each line should contain a single integer denoting the maximum score for the corresponding test case.

Sample Input 0

2
abcddcbd
abcd

Sample Output 0

3
0

Explanation 0

In the first case, we first collect "dd". The jewels now become "abccbd". Then collect "cc" followed by "bb". The jewels now become "ad", and no more jewels can be collected. The final score is , which is the maximum score possible.

In the second case, it is not possible to collect any jewels.

Line: 1 Col: 1
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score