Subprime Fibonacci Sequence

Time limit2sMemory limit512 MB

Summary

Generate terms with the divide-out recurrence and find the shortest repeating pair of consecutive terms within the first n terms, then print the cycle.

Level: Medium6 of 10
Topics: Simulation, Hash map, Number theory, Implementation
Solved: No attempts yet

Problem

The Subprime function $SP(n)$ of a positive integer $n$ is defined as follows.

$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 $a_n$ is defined by:

$a_0 \text{ and } a_1 \text{ are arbitrary}$ $a_{n+1} = SP(a_n + a_{n-1})$

For example:

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

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

Write a program that takes as input the initial values $a_0$ and $a_1$ and a number of terms to compute $n$ , and determines whether the sequence starting with $a_0$ and $a_1$ repeats in the first $n$ terms.

The sequence repeats if there are integers $k$ and $m$ with $k < m < n$ for which $a_k = a_m$ and $a_{k-1} = a_{m-1}$ .

The length of the repeating sequence is $(m - k)$ if there is no integer $j$ with $k < j < m$ such that $a_j = a_m$ and $a_{j-1} = a_{m-1}$ . That is, the sequence from $k$ to $m$ is the shortest repeating sequence.

Input

The first line of input contains a single decimal integer $P$ ( $1 \le P \le 1000$ ), the number of data sets that follow. Each data set is 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 \le 1000$ ) of terms to compute, followed by the initial values $a_0$ and $a_1$ in that order ( $0 < a_0, a_1 \le 1000$ ).

Output

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 $a_n$ of the sequence at $n$ (the $(n+1)$ -th term).

Examples1

Example 1

Input

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

Expected output

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