Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Big LCM

By curly_braces · Limits 2s, 512 MB

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

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

Input

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

The next $T$ lines each contains three integers $a, b, c (0 < a \leq b \leq 10^{18}$ and $1 < c \leq 10^{18})$.

Subtask Constraints

Subtask 1 (10% of points)

$0 < a \leq b \leq 10$
$1 < c \leq 10$

Subtask 2 (20% of points)

$0 < a \leq b \leq 32$
$1 < c \leq 10^5$

Subtask 3 (40% of points)

$0 < a \leq b \leq 10^5$
$1 < c \leq 10^9$

Subtask 4 (60% of points)

$0 < a \leq b \leq 10^9$
$1 < c \leq 10^9$

Subtask 5 (100% of points)

$0 < a \leq b \leq 10^{18}$
$1 < 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

    Discussion

    Statistics


    22% Solution Ratio

    riyad000Earliest, 3w ago

    Ahasan_1999Fastest, 0.0s

    riyad000Lightest, 131 kB

    prishan076Shortest, 1540B

    Submit

    Login to submit

    Editorial

    Subtask1-2 : Find the LCM, And see if LCM is divisible by ci or not. It can be seen that the LCM fi...