(String permutation) Write a recursive method to print all the permutations of a string. The user need to enter the string which consists of a set of characters.

입력 형식

First line of the input contains T (1 ≤ T ≤ 200), the number of test cases. For each test case, there will a string of characters, L (1 ≤ L ≤ 5).

출력 형식

For each test case, output a line in the format “Case # x:” where x is the case number (starting with 1), follow by the set of string permutation.

예제 입력

3
abc
zxyw
p7*

예제 출력

Case # 1:
abc
acb
bac
bca
cab
cba
Case # 2:
zxyw
zxwy
zyxw
zywx
zwxy
zwyx
xzyw
xzwy
xyzw
xywz
xwzy
xwyz
yzxw
yzwx
yxzw
yxwz
ywzx
ywxz
wzxy
wzyx
wxzy
wxyz
wyzx
wyxz
Case # 3:
p7*
p*7
7p*
7*p
*p7
*7p