A group of scientifically enhanced monkeys are tested in an experiment. There is a password protected door and behind it is the monkeys' dream: bananas!

The door password consists of N unique characters. The door security machine can give the monkeys hints in the form of a password string containing some characters to help them get the password faster. For example, “1**”.

The monkeys try a new password each hour. At most, for how many hours will they keep trying?

Write a program to find the maximum number of passwords that can be entered by the monkeys into the machine in order to get the bananas.

Input

Your program will be tested on one or more test cases. The first line of input will be a single integer T, the number of test cases (1<=T<=100).
Each test case starts with a line containing a single statement of consecutive characters (the password), each character can be an asterisk (‘*’) representing an unknown character or a reserved character which can be a single digit (‘0’...’9’) or a capital alphabetic character (‘A’...’J’). Note that the length of this statement will not exceed 20.

Output

For each test case, print “Case_#i:_X” where “X” represent the desired result, “i” is the number of the test case (starting with 1) and “_” is a white space. Each output should be printed in a separate line.

Example

Input:
3
1***7
G**9
D2******8

Output:
Case #1: 4896
Case #2: 306
Case #3: 8910720