KDIV - K-Divisors


The positive divisor function is defined as a function that counts the number of positive divisors of an integer N, including 1 and N.

If we define the positive divisor function as D(N), then, for example:

D(1) = 1

D(2) = 2

D(10) = 4

D(24) = 8

Calculating D(N) is a classical problem and there are many efficient algorithms for that. But what if you are asked to find something different? Given a range and an integer K, can you find out for how many N in the given range, D(N) equals K?

Input

In the very first line, you’ll have an integer called T. This is the number of test cases that shall follow. Every test case contains three integers, L, R, and K. L and R represent the range and are inclusive.

Constraints

  • 1 ≤ T < 31
  • 1 ≤ L ≤ R < 231
  • 1 ≤ K < 231
  • Output

    For every test case, you must print the case number, followed by the count of numbers with exactly K divisors in the range.

    Sample Input

    3
    10 10 4
    2 13 2
    100 10000 100
    

    Sample Output

    Case 1: 1
    Case 2: 6
    Case 3: 0
    


    Added by:sgtlaugh
    Date:2020-02-22
    Time limit:3s
    Source limit:50000B
    Memory limit:1536MB
    Cluster: Cube (Intel G860)
    Languages:All
    Resource:Own Problem