Amagi Brilliant Contests runs a business making and hosting contests on its online platform for competitive programmers who want to run their own contests.

Making a problem for a contest is a multi-step process. One of the steps involves having someone other than the problem writer independently solve the problem to make sure the author's test data and solution are correct.

One problem that has not yet been tested is as follows:

You are given three numbers , , and . How many numbers between and , inclusive, have exactly factors?

To refresh your memory, a factor of a number is a number such that and the remainder of the division is .

For this particular problem, there are a lot of cases the problem writer wants to test. Therefore, the problem tester will have to solve the aforementioned problem times.

You are the head of the number theory department at Amagi Brilliant Contests, and so you have been tasked with testing out this problem.

#### Constraints

There will be a number of subtasks for this problem:

Test Case Batch | Points (%) | |||
---|---|---|---|---|

1 | 5 | |||

2 | 5 | |||

3 | 5 | |||

4 | 5 | |||

5 | 5 | |||

6 | 5 | |||

7 | 5 | |||

8 | 5 | |||

9 | 5 | |||

10 | 5 | |||

11 | 5 | |||

12 | 5 | |||

13 | 10 | |||

14 | 10 | |||

15 | 20 |

#### Input Specification

The first line of input will have , the number of instances of the problem you need to solve.

Each of the next lines will contain three integers each separated from one another by a single space, , , and .

#### Output Specification

There should be lines of output. Each line should be a single integer, the answer to the problem with the given input.

#### Sample Input

```
3
1 1 30
2 1 30
3 1 30
```

#### Sample Output

```
1
10
3
```

#### Explanation for Sample Input

For the first case, the only number that has factor is .

For the second case, the numbers that have factors are , , , , , , , , , and .

For the third case, the numbers that have factors are , , and .

#### Hint

For users using the Python language, it is advised to use fast input/output methods such as those described on the tips page.

## Comments

Any hints on how not to TLE? or at least hints on what i'm doing wrong? I'm pretty sure i did the fast input thing correctly.

Precompute to handle queries in constant time.

This comment is hidden due to too much negative feedback. Click here to view it.