Conditionally rich numbers

시간 제한0.18초메모리 제한1024 MB

요약

각 질의 (L, R, V)에 대해 L 이상 R 이하의 정수 중 진약수의 합이 V보다 큰 수의 개수를 구한다.

난이도: 보통10점 중 6점
유형: 정수론, 누적 합, 정렬, 이분 탐색
정답자: 아직 제출이 없습니다

문제

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$

예제1

예제 1
입력
```
3
5 15 5
1 20 20
12 20 10
```
예상 출력
```
6
2
4
```