String Permutation

Write a recursive function that reads a string and prints all permutations of that string. The string consists of a set of distinct characters.

The first line contains $T$ ($1 \le T \le 200$), the number of test cases. Each of the next $T$ lines contains one string. Its length $L$ satisfies $1 \le L \le 5$, and it consists of distinct non-whitespace characters.

For each test case, first print a line in the format Case # x:, where x is the test case number starting from 1. Then print the permutations of the string, one per line.

Print the permutations in this order. Choose the first character from the characters of the input string, taking them in the order they appear in the input, and for each choice apply the same rule recursively to the remaining characters. For example, the permutations of abc are printed in the order abc, acb, bac, bca, cab, cba. The order depends on the positions of the characters in the input, not on alphabetical order.