Back

G. Almost Pisano

Worth 8 point(s) - Runtime Limit: 3 seconds

Summary

You are familiar with the Fibonacci sequence, 1,1,2,3,5,8,13, . . . etc. where
$$ Fi = F{i−1} + F{i−2}, F1 = F_2 = 1 $$
In 1960 Donald Wall of IBM discovered that \(Fn mod m\) repeats:

n         | 1 2 3 4 5 6 7 8 9 10 11 12 13
Fn        | 1 1 2 3 5 8 13 21 34 55 89 144 233
Fn mod 11 | 1 1 2 3 5 8 2 10 1 0 1 1 2

Let K(m) the length of the repeated subsequence. As we can see, K(11) = 10. Now consider the non-Fibonacci sequence:
$$ G_i = G_{i-1} + G_{i-2}, 0 <= G_1, G_2 <= 100 $$
Given integer values for \(G_1\), \(G_2\), and m determine if the sequence of \(G_i\mod m\) values repeats, and with what sequence length, K(m), \((1 ≤ G_1, G_2 ≤ 100)\), \((2 ≤ m ≤ 20)\)

Input

The first line of input contains a single decimal integer P,(1 ≤ P ≤ 500), which is the number of datasets that follow. Each dataset should be processed identically and independently. Each dataset consists one line of input containing the problem number, starting at 1, then follows the space-separated integer values of \(G_1\), \(G_2\) and m.

3
1 1 1 11
2 2 4 10
3 1 3 7

Output

For each dataset there will be one line of output. That line will begin with the problem number, then the value of K(m). If K(m) > 100 output 100 as its value.

1 10
2 20
3 16