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.

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)

For every Test Case, output one integer: the answer mod 10^9+7