Limits 2s, 512 MB

Let, BLCM(a,b)BLCM(a, b) be the smallest positive integer which is divisible by all integers in range [a,b][a, b].

Given 3 positive integers aa, bb and cc, find an integer nn for which BLCM(a,b)BLCM(a, b) is divisible by cnc^n. If there are more than one possible nn, find the largest one.

Input

Input starts with an integer TT (0<T1000 < T \leq 100) denoting number of test cases.

The next TT lines each contains three integers aa, bb, cc (0<ab10180 < a \leq b \leq 10^{18} and 1<c10181 < c \leq 10^{18}).

Output

For each test case, print an integer in one line containing your answer to that test case.

Sample

InputOutput
2
1 5 2
5 7 4
2
0

Submit

Login to submit.

Statistics

28% Solution Ratio
riyad000Earliest, Jul '20
Ahasan_1999Fastest, 0.0s
riyad000Lightest, 131 kB
bokaifShortest, 664B
Toph uses cookies. By continuing you agree to our Cookie Policy.