시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

The Subprime function, SP(n) of a positive integer n, is defined by:

SP(n) = n if n is 1 or a prime

Otherwise,

SP(n) = n/p where p is the smallest prime dividing n

A Subprime Fibonacci sequence, an, is defined by:

a0 and a1 are arbitrary
an+1 = SP(an + an-1)

For example:

0, 1, 1, 2, 3, 5, 4, 3, 7, 5, 6, 11, 17, 14, 31, 15, …

Unlike the standard Fibonacci sequence which grows exponentially, a Subprime Fibonacci sequence usually eventually repeats.

Write a program which takes as input the initial values a0 and a1 and a number of terms to compute n and determines whether the sequence starting with a0 and a1 repeats in the first n terms.

The sequence repeats if there are integers k and m with k < m < n for which,

ak = am and ak-1 = am-1

The length of the repeating sequence is (m – k) if there is no integer j, k < j < m with aj = am and aj-1 = am-1. I.e. the sequence from k to m is the shortest repeating sequence.

입력

The first line of input contains a single decimal integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input. It contains the data set number, K, followed by the maximum number, n (0 < n ≤ 1000), of terms to compute followed by the initial values a0 and a1 in that order, (0 < a0, a1 ≤ 1000).

출력

For each data set there are multiple lines of output.

If a repeating sequence is found, the first line of output contains the data set number, K, followed by the index m where the sequence first repeated followed by the length of the shortest repeating subsequence. The following lines of output contain the (length + 2) terms of the sequence from term (k-1) to term (m), 20 terms to a line (except possibly for the last line).

If a repeating sequence is not found in the first n terms, the first line of output contains the data set number, K, followed by the number of terms n followed by the digit 0. The following line contains only the value an of the sequence at n (the (n+1)th term).

예제 입력 1

3
1 1000 0 1
2 10 31 23
3 200 15 17

예제 출력 1

1 57 18
48 13 61 37 49 43 46 89 45 67 56 41 97 69 83 76 53 43 48 13
2 10 0
88
3 137 136
15 17 16 11 9 10 19 29 24 53 11 32 43 25 34 59 31 45 38 83
11 47 29 38 67 35 51 43 47 45 46 13 59 36 19 11 15 13 14 9
23 16 13 29 21 25 23 24 47 71 59 65 62 127 63 95 79 87 83 85
84 13 97 55 76 131 69 100 13 113 63 88 151 239 195 217 206 141 347 244
197 147 172 29 67 48 23 71 47 59 53 56 109 55 82 137 73 105 89 97
93 95 94 63 157 110 89 199 144 49 193 121 157 139 148 41 63 52 23 25
24 7 31 19 25 22 47 23 35 29 32 61 31 46 11 19 15 17