It is an easy problem. You are given a string (without any spaces) and you should find the sum of the string's characters' ASCII value.

You have to remove all duplicate characters from the string.

For example:

SSsssstttrriiinnng = Sstring
HELLO = HELO

Input

The input consists of N<=20 cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists a string S without any spaces. The length of the S could be around 1000, includind special characters.

Output

For each cases you should print case number and sum of string's ASCII value in binary, and print new line for every test case.

Example

Input:
2
HELLO
SSSPPPOOOJJJ

Output:
#1 : 100101000
#2 : 100111100