primacity-hard

Primacity of an integer is the number of distinct primes which divide it. For example, the primacity of 12 is 2 (as it's divisible by primes 2 and 3).

Given 3 integers A, B, and K, how many integers in the inclusive range [A, B] have a primacity of exactly K?
Input

Input begins with an integer T, the number of test cases. For each case, there is one line containing 3 space-separated integers: A, B, and K. 
Constraints
 
1 ≤ T ≤ 10^5

2 ≤ A ≤ B ≤ 10^7

1 ≤ K ≤ 10^9

SAMPLE INPUT
5
5 15 2
2 10 1
24 42 3
1000000 1000000 1
1000000 1000000 2

SAMPLE OUTPUT
5
7
2
0
1

Source: hackerearth | Difficulty: MEDIUM


Solutions: