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.

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.