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
2 ≤ A ≤ B ≤ 10⁷
1 ≤ K ≤ 10⁹