# Simple

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