Counting Divisors

Problem Description

In mathematics, the function $d(n)$ denotes the number of divisors of positive integer $n$. For example, $d(12)=6$ because $1,2,3,4,6,12$ are all $12$'s divisors. In this problem, given $l,r$ and $k$, your task is to calculate the following thing :

Input

The first line of the input contains an integer $T(1\leq T\leq15)$, denoting the number of test cases. In each test case, there are $3$ integers $l,r,k(1\leq l\leq r\leq 10^{12},r-l\leq 10^6,1\leq k\leq 10^7)$.

Output

For each test case, print a single line containing an integer, denoting the answer.

Sample Input

3

1 5 1

1 10 2

1 100 3

Sample Output

10

48

2302

Source

2017 Multi-University Training Contest - Team 4

https://acm.hdu.edu.cn/showproblem.php?pid=6069