Buy1Get1

All submissions for this problem are available.
One day Alice visited Byteland to purchase jewels for her upcoming wedding anniversary.
In Byteland, every Jewelry shop has their own discount methods to attract the customers. One discount method called Buy1Get1 caught Alice's attention. That is, Alice buys one jewel, then she can get one additional jewel with the same color without charge by Buy1Get1.
Alice lists the needed jewels as a string S, each letter denotes one jewel, and the same letters denote the same colors of jewels, and the different letters denote the different colors of jewels. The cost of each jewel is 1. Your task is to calculate the minimum cost for getting all the jewels Alice listed.
Input
The first line of input contains a single line T, which represents the number of test cases. Then T lines will follow, and each contains a string S, which represents the jewels Alice needed.
Output
Output the minimum cost for each test case.
Constraints
1 ≤ T ≤ 100
1 ≤ S ≤ 200, where S represents the length of the string S.
The string S is case sensitive, and will contain only English characters in the range [az], [AZ].
Sample
Input: 4 ssss ssas sa s Output: 2 3 2 1
Explanation
In the first sample case, Alice needs 4 jewel of color s. One of the optimal way is the following:
Buy the first s with cost 1, and she can get the second s without charge. Then buy the third s with cost 1, and she can get the last s without charge. In this case, she get 4 jewels with only cost 2.
In the second sample case, Alice needs 3 jewels of color s and 1 jewel of color a. One of the optimal way is the following:
Buy the second s with cost 1, and she can get the last s without charge. Then buy the a and the first s with cost 2. In this case, she get 4 jewels with only cost 3.
In the third and fourth sample cases, she cannot save her money by using Buy1Get1.
Author:  khadarbasha 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/BUY1GET1 
Tags  adhoc cakewalk feb13 khadarbasha 
Date Added:  4092012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 