Adam’s parents put up a sign that says “COMBINATORICS”. The sign is so big that exactly one letter fits on each panel. Some of Adam’s younger cousins got bored during the reception and decided to rearrange the panels. How many unique ways can the panels be arranged (counting the original arrangement)?

Input

First line contains a single integer T(less than 1000) denoting the total number of test cases.

Each test case contains a string S having atmost 15 characters from A to Z.

Output

For each word, output the number of unique ways that the letters can be rearranged (counting the original arrangement). Use the format shown in Sample Output, below.

Example

Input:
3
HAPPY
WEDDING
ADAM

Output:
Case 1: 60
Case 2: 2520
Case 3: 12