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
| Input | Output |
|---|---|
2 1 5 2 5 7 4 | 2 0 |
