题目描述

给你A,B,N三个数，问你在A，B之间（include），有多少个数与N互质。

公约数只有1的两个数,叫做互质数。

输入格式

两行。第一行包含T（0<T<=100）测试用例的数量，接下来的每一行包含三个整数A，B，N，其中（1<=A<=B<=1015）和（1<=N<=109）。

输出格式

对于每个测试用例，打印A和B之间的相对于N是素数的整数（包括A和B）的个数。遵循下面的输出格式。

样例数据

input

2
1 10 2
3 15 5

output

Case #1: 5
Case #2: 10