# 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 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

### Statistics

22% Solution Ratio

Ahasan_1999Fastest, 0.0s

prishan076Shortest, 1540B