Bazinga
题号:NC15330
时间限制:C/C++/Rust/Pascal 3秒,其他语言6秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

There is a formula:

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:


输入描述:

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 and K.

• 1 ≤ T ≤ 20.

• 1≤ L ≤ R ≤1018
• 1 ≤ K ≤ 105.


输出描述:

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.
示例1

输入

复制
2
1 5 6
10 20 8

输出

复制
Case #1: 5
Case #2: 3

备注:

For the first case, answer = (1×5) mod 6 = 5.
For the second case, answer = (11×13×15×17×19) mod 8 = 3.