타자기 원숭이 (Small)

어떤 출판사가 원숭이에게 무작위로 자판을 두드리게 해서 문학 작품을 만들기로 했다. 원숭이가 쓰는 자판에는 키가 $K$개 있고, 키마다 영어 대문자가 하나씩 적혀 있다. 같은 글자가 적힌 키가 여러 개 있을 수도 있다.

원숭이는 빈 문자열에서 시작해 다음을 $S$번 반복한다. 자판에서 키 하나를 같은 확률로 골라 누르고, 그 키의 글자를 문자열 오른쪽 끝에 덧붙인다. 그래서 최종 문자열의 길이는 $S$다.

당신에게는 길이가 $L$인 목표 단어가 있다. 실제로 쓰이는 영어 단어일 필요는 없다. 목표 단어는 원숭이가 친 문자열에 여러 번 나타날 수 있고, 겹쳐서 나타난 것도 각각 센다. 목표 단어가 ABA이고 원숭이가 ABABA를 쳤다면 등장 횟수는 2다.

당신은 목표 단어가 한 번 나올 때마다 바나나를 하나씩 준다. 원숭이의 결과물을 보러 갈 때는 원숭이가 무엇을 쳤든 바나나가 모자라지 않도록 필요한 최소 개수를 가져간다. 즉 이 자판으로 칠 수 있는 길이 $S$의 문자열이 목표 단어를 가질 수 있는 최대 등장 횟수만큼 가져간다. 그다음 실제로 친 문자열의 등장 횟수만큼 바나나를 주고, 남은 바나나는 당신이 가진다.

당신이 가지게 될 바나나 개수의 기댓값을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 세 줄로 이루어진다. 첫 줄에는 정수 $K$, $L$, $S$가 공백으로 구분되어 주어진다. 둘째 줄에는 원숭이의 자판을 나타내는 길이 $K$의 영어 대문자 문자열이 주어진다. 셋째 줄에는 목표 단어를 나타내는 길이 $L$의 영어 대문자 문자열이 주어진다.

제한

• $1 \le T \le 100$
• $1 \le K \le 7$
• $1 \le L \le S \le 7$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 당신이 가지게 될 바나나 개수의 기댓값이다. $y$는 소수점 아래 여섯 자리까지 반올림해서, 여섯 자리를 모두 채워 출력한다. 주어진 제한에서 정답이 반올림 경계에 정확히 놓이는 일은 없다.