rich_num

Mariya has come up with the following definition for a rich number. It is given a positive integer $X$. Then a positive integer $N$ is called a rich number (relative to $X$) if the sum of its divisors except $N$ is greater than $X$. For example, the number $10$ (whose sum of divisors is $1+2+5 = 8$) is rich relative to $X=7$ but it isn't rich relative to $X=12$.

Task

Write a program to help Mariya. The program will be given queries that are ordered triples of positive integers $(L, R, V)$ and for each query it should calculate the number of rich numbers relative to $V$, which are greater than or equal to $L$ and less than or equal to $R$.

Input

The first line of the standard input contains one positive integer $Q$ — the number of queries that your program has to process.

Each of the next $Q$ lines contains three positive integers $L$, $R$ and $V$, which describe a query for your program to process.

Output

Your program should output to the standard output $Q$ lines — one line for each query in the order of the input. Each line should contain the answer to the corresponding query.

Constraints

• $1 ≤ Q ≤ 10^5$
• $1 ≤ L ≤ R ≤ 10^5$
• $1 ≤ V ≤ 10^5$

Subtasks

Subtask 1 (5 points)

• $Q \le 10^3$
• $R \le 10^3$

Subtask 2 (10 points)

• $R \le 10^4$
• $V = 10$

Subtask 3 (30 points)

• $V \le 10$

Subtask 4 (55 points)

• No additional constraints

Example

stdin

3
5 15 5
1 20 20
12 20 10

stdout

6
2
4