28485번 - Conditionally rich numbers 서브태스크다국어

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$.

Write a program rich_num 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$.

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.

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.

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