Special Square Number

All submissions for this problem are available.
A special square number is a number containing the digits 09 such that 0 can occur any number of times while the other digits 19 must occur squared times. E.g. 1 must occur 1x1 times, 2 must occur 2x2 times… 9 must occur 9x9 times. The digits may be ordered in any way and it need not be the case that the all same digits be consecutive. Some examples of special square numbers are 1, 12222, and 301333333223322.
Your task is to accept a number and convert it into a special square number containing all the digits that exist in the input number i.e. if the input number has only digits 1 and 2 , the special square number must contain only the digits 1 and 2. Care must be taken that the same no. of zeros appear in the special square number after conversion as in the original number. You can perform the following operations each having a particular cost.
 Replace an existing digit with another cost: 1
 Add a new digit cost: 4
 Delete an existing digit cost: 8
You are required to write a program in such a way that the input number must be converted into a special square number with minimum cost using any operations.
Input
 The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows"
 A single integer N for each test case
Output
T lines giving minimum cost for conversion of each N to corresponding special square number in order of test cases.
Constraints
 1 ≤ T ≤ 10
 1 ≤ (no. of digits in N) ≤ 1000
Example
Input: 3 1 1122 333033322222223 Output: 0 5 10
Explanation
First line of input specifies that there are 3 test cases. The next 3 lines which follow each input a number.
For 1, the minimum cost is 0 as it already is a special square number.
For 1122, a 1 is extra while we need two more 2s. So the minimum cost is obtained if we replace a 1 by 2 (cost 1) and add an extra 2 (cost 4). So, minimum cost 5 is output.
For 333033322222223, there can be any no. of zeroes. There are seven 3s and seven 2s. So, we replace two 2s by 3s (cost 2x1) and delete a 2 (cost 8). So, minimum cost is 10.
Author:  rkp7 
Tags  rkp7 
Date Added:  2102014 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS 
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. 