It is known that the number is called perfect if it equals the sum of all its positive divisors except himself. For example, the first perfect number – 6 = 1 + 2 + 3. We now state this more rigorously, we consider the function:
The number is perfect if and only if σ(n) – n = 0.
Is the number of k-perfect if |σ(n) – n| = k. Thus, 2-perfect numbers are, for example, 3 and 10. Your task is to find the number of k-perfect numbers on the interval [l, r].
The first line of the input file contains the number of tests t (1 ≤ t ≤ 100000). Each test consists of one line containing three integers l, r and k, separated by single spaces (1 ≤ l ≤ r ≤ 10^6, 0 ≤ k ≤ 10^9).
For each test case output a string containing the number of k-perfect numbers on the interval [l, r].