The Garage Sale
The chef has a friend who is a mathematician. His friend is having a garage sale. The person being a mathematician, created an interesting scheme for the sale.
The scheme as stated by chef’s friend is as follows:
There are different types of items available for the sale. A person can buy a number of these items. From the items that will be purchased, the type of item which has the most frequency was found out and that particular frequency was recorded.
Now, if this recorded number is a prime number, then half of the items of the item type that has a prime number frequency will be given as free and if the recorded number is a composite number, then half of the items of the item type that has a composite frequency will be given as free.
You need to help the chef’s friend in finding the final bill generated after all the deductions according to the scheme as stated above.
You need to do this for a number of test cases.
The cost of each item is $1.
The items are depicted with use of characters (a-z, A-Z ), i.e., the items of same type are depicted with the same character. For an odd number, say n the value of n/2 is the value obtained after passing n/2 through the greatest integer function. For example: 11/2 will be 5.
The first line contains the number of test cases t, that is, the number of people who purchase from the garage sale.
The first and the only line of each test case contains a string s, the items purchased (containing a-z, A-Z ) by a person.
The output for each test case contains an integer in a separate line denoting the total amount paid by the person after the deductions being made according to the garage sale.
1<= t<= 100
Input: 3 abcdefghig aabbccddddef Aabcdef Output: 9 10 7
Example case 1. The frequency of 'g' is maximum, i.e., 2. The frequency of only 'g' is prime so half of items of type 'g' will be free. So, 1 item will be free.
Example case 2. The frequency of 'd' is maximum, i.e., 4, which is a composite number. The frequency of only 'd' is composite so half of items of type 'd' will be free. So, 2 items will be free.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions