#1741 N-substring

35  10 s   128 MB  

Description

알파벳 대문자로만 이뤄진 문자열이 주어졌을 때   N-substring을 구하는 프로그램을 작성하라.

N-substring이란 길이가 N인 부분 문자열을 뜻한다. 부분 문자열이란 문자열 내에서 연속된 부분으로 이뤄진 문자열을 뜻한다.

Input

입력의 첫째 줄에는 테스트 케이스의 개수 T ( 0 < T <= 100 )이 입력된다.

그 다음 줄 부터 T개의 줄에는 N-substring의 N과 1,000자 이하의 알파벳 대문자로 이뤄진 문자열이 입력된다. N은 항상 문자열의 길이보다 작거나 같게 입력된다.

Output

각 테스트 케이스에 대해 다음과 같은 형태로 출력한다.

Case #X:
NS1
NS2
...

여기서 X는 테스트 케이스의 순서를 뜻하며 1부터 시작한다. NS1, NS2, ... 는 문자열에 포함된 N-substring을 뜻한다.

N-substring을 중복 되지 않게 사전 순으로 출력한다.

Sample Input

Sample Output

4
1 ABCD
2 ABCD
4 ABCD
1 BAAA
Case #1:
A
B
C
D
Case #2:
AB
BC
CD
Case #3:
ABCD
Case #4:
A
B