Description
Given f1, f2… fn denoting the frequencies of n different symbols to be encoded into variable length binary representation using Huffman encoding. Let d1, d2… dn denote the encoded length of the symbols. Please find the optimal encoding, which means that the average length of the encoded message
is minimized.
Input
The first line of the input consists of an integer T (T ≤ 1000) denoting the number of test cases. Each test case starts with an integer N (N ≤ 10000) representing the number of symbols to be encoded, and the following are N integers corresponding to the frequencies of the symbols.
Output
For each test case, output “Case i:”, where i is the sequence number starting from 1, and then the minimized average length of the encoded message, rounded to two decimal places.