[2018 SCPC 본선]

외계메시지

외계인이 존재하는가는 사람들이 오랫동안 궁금해온 문제이다.

김박사는 삼성전자의 후원을 받아서 특정한 별에 외계인이 존재하는지 연구를 진행하고 있다.

이 연구로 외계인을 발견한다면 인류의 모든 지식에 큰 변화가 올 것이다. 



이 별이 연구의 대상이 된 이유는 별의 밝기가 매 시간마다 변하기 때문이다.

처음에는 단순한 변광성으로 생각하였지만, 그러기에는 밝기의 변화에 반복이 자주 발생한다는 것을 알아냈기에 현재로서는 이 별에 고도의 문명이 존재하여, 별의 밝기를 조절할 수 있다는 의견이 대다수이다.

고성능 전파망원경 하나가 이 별을 쫓아다니면서 매 시간마다 별의 밝기를 기록한다.

이 밝기는 1 이상 255 이하의 정수로 정규화되어 기록된다.

매 시간 별의 밝기를 기록한 개의 정수가 주어졌을 때, 김박사는 이 밝기의 변화가 우연인지 아닌지 알기 위해서 번 이상 반복되어 나오는 패턴이 있는지를 효율적으로 찾고 싶어 한다.



예를 들어,  이고 2, 1, 4, 1, 4, 1이 전파망원경의 입력이라고 하자.

라고 하면, 입력 중 두 번 이상 나오는 패턴을 찾아보면 길이가 1인 패턴은 1, 4, 길이가 2인 패턴은 1, 4 그리고 4, 1, 길이가 3인 패턴은 1, 4, 1이다.

김박사의 생각으로는 연속하여 나타나면서 두번 이상 나타나는 가장 긴 패턴이 가장 큰 의미를 갖는다.

따라서 이 경우 답은 1, 4, 1이다.

1, 4, 1이 두 번 나타날때 서로 교차할 수 있는데 주의하라.

이라면 세 번 이상 반복되어 나온 패턴은 1 뿐이며, 라고 하면 만족하는 패턴이 없다.



구체적으로 어떤 패턴이 나타나는지보다 이 패턴의 길이가 더 의미가 크기 때문에,

일때 원하는 답은 3 (만족하는 패턴이 1, 4, 1),  일때 원하는 답은 1 (만족하는 패턴이 1),  일때 원하는 답은 0 (만족하는 패턴이 없음)이다. 

시간의 별의 밝기 측정 값, 패턴의 반복 횟수  가 주어졌을 때, 번 이상 반복하여 나타나는 패턴 중 가장 긴 패턴의 길이를 구하는 프로그램을 작성하시오.




입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 가 주어지고,

이후 차례로    개의 테스트 케이스가 주어진다. ()

각 테스트 케이스의 첫 줄에는 두 개의 정수 , 이  순서대로 주어지며 각각은 측정한 별의 밝기 데이터의 크기, 패턴이 나타나야 하는 최소 횟수를 나타낸다. 

다음 줄에는 일간 측정한 별의 밝기 데이터가 주어진다.

이는 개의 정수로 표현되는데, 각각의 수는 1 이상 255 이하이다.




출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,

각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 는 테스트 케이스의 번호이다.

그 다음 줄에 입력으로 받은 별의 밝기 데이터에서 주어진 횟수 이상  나타나는 가장 긴 문자열의 길이를 출력한다.

만약 조건을 만족하는 문자열이 없다면, 숫자 0을 출력한다. 

입출력예

입력
2
6 2
2 1 4 1 4 1
6 4
2 1 4 1 4 1
출력
Case #1
3
Case #2
0

돌아가기