소문자로만 구성된 문자열 S와 정수 k가 주어지면 S의 부분 문자열 중 부분 문자열의 모든 문자의 빈도수가 k 이상인 가장 긴 부분 문자열의 길이 찾아 주세요. 예를 들어 "mmmxx'"와 k = 3이 주어지면 "mmm"이 이 조건을 만족하는 가장 긴 부분 문자열이므로 3을 반환해야 합니다.

첫 줄에는 테스트케이스 T(1<=T<=1,000)가 주어집니다. 그다음 두 줄에 각 테스트케이스가 주어집니다. 첫 줄에는 문자열 S(1<=len(S)<=10,000)가 주어지고, 둘째 줄에는 정수 k(1<=k<=10,000)가 주어집니다. 주어지는 문자열 S는 모두 소문자로만 구성되어 있습니다.

각 테스트케이스마다 모든 문자가 k번 이상 등장하는 가장 긴 부분 문자열의 길이를 출력합니다.