#1742 N-substring 2

16  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 F1
NS2 F2
...

여기서 X는 테스트 케이스의 순서를 뜻하며 1부터 시작한다. NS1, NS2, ... 는 문자열에 포함된 N-substring을 뜻하고, F1, F2... 는 각 N-substring의 빈도수를 뜻한다. N-substring이 여럿 있을 경우 사전순으로 출력한다. 

Sample Input

Sample Output

3
1 ABCD
2 ABCD
2 AAAA
Case #1:
A 1
B 1
C 1
D 1
Case #2:
AB 1
BC 1
CD 1
Case #3:
AA 3