문자열 순열

문자열을 입력받아 그 문자열의 모든 순열을 출력하는 재귀 함수를 작성하시오. 문자열은 서로 다른 문자의 집합으로 이루어진다.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 200$)가 주어진다. 이어서 각 테스트 케이스마다 한 줄에 문자열 하나가 주어진다. 문자열의 길이 $L$은 $1 \le L \le 5$이고, 문자열은 공백이 아닌 서로 다른 문자로 이루어진다.

각 테스트 케이스마다 먼저 Case # x: 형식으로 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이다. 그다음 줄부터 문자열의 순열을 한 줄에 하나씩 출력한다.

순열은 다음 순서로 출력한다. 첫 글자로 입력 문자열의 문자를 입력에 나타난 순서대로 하나씩 고르고, 고른 문자마다 남은 문자들로 같은 방법을 재귀적으로 적용한다. 예를 들어 abc의 순열은 abc, acb, bac, bca, cab, cba 순서로 출력한다. 이 순서는 알파벳 순서가 아니라 입력에서 문자의 위치를 기준으로 한다.