Big LCM

Let, $BLCM(a, b)$ be 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}$).

Output

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

Sample

2
1 5 2
5 7 4

2
0