MCS

현대 분자생물학에서 유전 정보는 모두 DNA로 인코딩되어 표현된다. 컴퓨터 과학에서는 DNA를 {A, G, T, C} 네 가지 문자로만 이루어진 매우 긴 문자열로 나타낸다.

어떤 DNA 패턴(부분문자열)이 다른 것보다 더 자주 나타나는지를 찾는 일은 유전병 연구에서 매우 중요하다. 이 문제에서는 합성적으로 같은(compositionally equivalent) 부분문자열을 다룬다. 두 문자열 P와 Q에 등장하는 네 문자 A, G, T, C의 개수가 각각 모두 같으면, P와 Q는 합성적으로 같다고 한다. 예를 들어 P = "ATTATGC"와 Q = "GTATCTA"는 각 문자의 개수가 서로 같으므로 합성적으로 같다. 반면 "TTGCA"와 "TGCCA"는 합성적으로 같지 않다.

길이가 k인 부분문자열들 중에서 서로 합성적으로 같은 것끼리 묶었을 때, 가장 큰 묶음에 속하는 부분문자열을 k-MCS(k-Major Composition Substring)라고 한다. 여기서 k-부분문자열은 길이가 k인 부분문자열을 뜻한다. 하나의 DNA 문자열에서 k-MCS는 유일하지 않을 수도 있다.

예를 들어 길이가 14인 DNA 문자열 W = "GCAGGAGCGCCAGG"에서 k = 3인 경우, "AGG"와 합성적으로 같은 부분문자열(AGG, GGA, GAG, AGG)은 모두 4번 등장한다. W에서 이보다 더 자주 등장하는 합성 묶음은 없으므로, 이 문자열의 3-MCS는 4번 등장한다.

DNA 문자열 W와 정수 k가 주어질 때, k-MCS가 몇 번 등장하는지 구하는 프로그램을 작성하시오. 즉, 길이가 k인 모든 부분문자열을 합성적으로 같은 것끼리 묶었을 때 가장 큰 묶음의 크기를 출력하면 된다.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어지며, 정수 k와 DNA 문자열 W가 공백으로 구분되어 주어진다 ($1 \le k \le 600$, $10 \le |W| \le 60000$). W는 문자 A, G, T, C로만 이루어져 있다.

각 테스트 케이스마다 주어진 W에서 k-MCS가 몇 번 등장하는지를 한 줄에 하나씩 출력한다. 만약 k가 |W|보다 크면 길이가 k인 부분문자열이 존재하지 않으므로 0을 출력한다.