11007: Bazinga
[Creator : ]
Description
There is a formula:
Give you three integers $L, R$ and $K$. Please calculate the value of the following formula:
$(\prod_{x=L}^{R}f(x,K)) \bmod\ K$.
$f(a,b)=\left\{\begin{aligned}a&\text{gcd}(a,b)&=1\\1&\text{gcd}(a,b)& \neq 1\end{aligned}\right.$
$\text{gcd}(a, b)$ is the greatest common divisor of $a$ and $b$. Give you three integers $L, R$ and $K$. Please calculate the value of the following formula:
$(\prod_{x=L}^{R}f(x,K)) \bmod\ K$.
Input
The first line contains an integer $T$, where $T$ is the number of test cases. $T$ test cases follow.
For each test case, the only line contains three integers $L, R, K$.
Output
For each test case, output one line containing “Case #x: y”, where $x$ is the test case number (starting
from $1$) and $y$ is the answer.
Constraints
$1 ≤ T ≤ 20$
$1≤ L ≤ R ≤10^{18}$
$1 ≤ K ≤ 10^5$
$1≤ L ≤ R ≤10^{18}$
$1 ≤ K ≤ 10^5$
Sample 1 Input
2
1 5 6
10 20 8
Sample 1 Output
Case #1: 5
Case #2: 3
For the first case, answer = $(1×5) \bmod\ 6 = 5$.
For the second case, answer = $(11×13×15×17×19) \bmod\ 8 = 3$.
For the second case, answer = $(11×13×15×17×19) \bmod\ 8 = 3$.