Limits 4s, 512 MB

Given three integers m,n,b (m<n)m, n, b\space (m < n), let’s consider the representation of m/nm/n in base bb. Since m<nm < n, resulting in m/n<1m/n < 1, the representation will be: s=0.s1s2s3s = 0.s_1s_2s_3\dots.

Sometimes the representation can be finite, sometimes it is not. If infinite, sometimes it repeats, and sometimes it does not. When it repeats, sometimes it starts repeating from a certain position, not at the beginning, or sometimes at the beginning.

In this problem, for any given m,n,bm, n, b, you need to find the type of representation, and if it repeats then the length of the representation along with the starting position of the repetition.

Input

The first line contains an integer T(0<T<500001)T \, (0 < T < 500001) denoting the number of test cases.

Each of the next TT lines contains three space-separated integers mm, nn, and b(0<m<n5×106,1<b5×106)b \, (0 < m < n \le 5 \times10^6, 1 < b \le 5 \times10^6). All test cases are randomly generated, and all input numbers are in base 10.

Output

For each case, if the representation is finite then print "finite" without quotes and the length of the representation separated by space.

If the representation is infinite, then if there is no repetition then print "infinite -1\text{-}1" without quotes. If there is repetition, then print "infinite SLS \, \, L" without quotes where SS is the length of the representation string before repetition and LL is the length of repetition.

Sample

InputOutput
3
1 2 10
1 3 10
1 6 10
finite 1
infinite 0 1
infinite 1 1

This numerical representation of fractions is not well-defined. That is two different numerical representations can represent the same number. For example, 0.999990.99999\dots and 11 represent the same number. In such cases, use the finite representation. Another more concrete example is for the first sample input “1 2 10”, 1/2 = 0.5 in base 10 or one could say, 1/2 = 0.4999999…. In such cases consider 1/2=0.5 which is the finite numerical representation of 1/2 in base 10.

Submit

Login to submit.

Statistics

0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.