서브프라임 피보나치 수열

양의 정수 $n$에 대한 서브프라임 함수 $SP(n)$은 다음과 같이 정의된다.

• $n$이 1이거나 소수이면 $SP(n) = n$
• 그렇지 않으면 $SP(n) = n/p$. 여기서 $p$는 $n$을 나누는 가장 작은 소수이다.

서브프라임 피보나치 수열 $a_n$은 다음과 같이 정의된다.

$a_0, a_1 \text{은 임의의 값}$ $a_{n+1} = SP(a_n + a_{n-1})$

예를 들어:

$0, 1, 1, 2, 3, 5, 4, 3, 7, 5, 6, 11, 17, 14, 31, 15, \ldots$

지수적으로 증가하는 일반적인 피보나치 수열과 달리, 서브프라임 피보나치 수열은 보통 언젠가 반복된다.

초기값 $a_0$과 $a_1$, 그리고 계산할 항의 수 $n$을 입력으로 받아, $a_0$과 $a_1$로 시작하는 수열이 처음 $n$개 항 안에서 반복되는지 판별하는 프로그램을 작성하라.

$k < m < n$인 정수 $k$와 $m$에 대해 $a_k = a_m$이고 $a_{k-1} = a_{m-1}$이면 수열이 반복된다고 한다.

반복 수열의 길이는, $k < j < m$이면서 $a_j = a_m$이고 $a_{j-1} = a_{m-1}$인 정수 $j$가 없을 때 $(m - k)$이다. 즉, $k$부터 $m$까지의 수열이 가장 짧은 반복 수열이다.

입력의 첫 줄에는 데이터 세트의 수 $P$ ($1 \le P \le 1000$)가 주어진다. 각 데이터 세트는 서로 독립적으로 동일하게 처리된다.

각 데이터 세트는 한 줄로 주어진다. 데이터 세트 번호 $K$, 계산할 항의 최대 개수 $n$ ($0 < n \le 1000$), 초기값 $a_0$과 $a_1$이 순서대로 주어진다 ($0 < a_0, a_1 \le 1000$).

각 데이터 세트에 대해 출력은 여러 줄이다.

반복되는 수열을 찾으면, 출력의 첫 줄에는 데이터 세트 번호 $K$, 수열이 처음 반복된 인덱스 $m$, 가장 짧은 반복 부분 수열의 길이가 주어진다. 그다음 줄들에는 $k-1$번째 항부터 $m$번째 항까지의 (길이 + 2)개 항이 주어지며, 한 줄에 20개씩 출력한다 (마지막 줄은 예외일 수 있다).

처음 $n$개 항 안에서 반복되는 수열을 찾지 못하면, 출력의 첫 줄에는 데이터 세트 번호 $K$, 항의 개수 $n$, 숫자 0이 주어진다. 그다음 줄에는 $n$에서의 수열 값 $a_n$ (즉 $(n+1)$번째 항)만 출력한다.