All Submissions


Your task is simple. Given a range [x,y] you need to find out the number of integers in this range whose smallest divisor, apart from 1, is z.

INPUT
The first line of input contains the number of test cases T.
Each test case contains three integers x, y and z.

OUTPUT
For each test case print the number of such integers in separate line.

CONSTRAINT

T <= 100
1 <= x <= 2*10^9
1 <= y <= 2*10^9
2 <= z <= 2*10^9


SAMPLE INPUT

3
1 10 2
12 23 3
6 19 5


SAMPLE OUTPUT

5
2
0


Problem Setter : Akshay Kumar


Languages: Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 7 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0