Find the First Zero in a Modular Fibonacci-like Sequence

Consider a sequence defined as follows:

\(F_0 = a, \quad F_1 = b, \quad F_i = (F_{i-1} + F_{i-2}) \bmod m \quad \text{for } i \ge 2\).

Given n queries, each providing values for \(a\), \(b\), and \(m\), your task is to determine the smallest non-negative integer \(p\) such that \(F_p = 0\). Note that the sequence might reach 0 at the very beginning, so be sure to check \(F_0\) and \(F_1\) as well.

inputFormat

The first line contains an integer n (1 ≤ n), which is the number of queries.

Each of the following n lines contains three integers \(a\), \(b\), and \(m\) where \(a\) and \(b\) are the first two terms of the sequence and \(m\) is the modulus.

outputFormat

For each query, output a single line containing the smallest index \(p\) such that \(F_p = 0\).

sample

1
1 1 2

2