[2017年杭电多校]Senior PanⅡ
Senior Pan¢ò
Problem Description
Senior Pan had just failed in his math exam, and he can only prepare to make up for it. So he began a daily task with Master Dong, Dong will give a simple math problem to poor Pan everyday. But it is still sometimes too hard for Senior Pan, so he has to ask you for help. Dong will give Pan three integers L,R,K every time, consider all the positive integers in the interval [L,R], you¡¯re required to calculate the sum of such integers in the interval that their smallest divisor (other than 1) is K.
Input
The first line contains one integer T, represents the number of Test Cases. Then T lines, each contains three integers L,R,K(1<=L<=R<=10^11,2<=K<=10^11)
Output
For every Test Case, output one integer: the answer mod 10^9+7
Sample Input
2
1 20 5
2 6 3
Sample Output
Case #1: 5
Case #2: 3
Source
2017 Multi-University Training Contest - Team 9