PRSQRFR - Perfect Composites

Rohil and Mahesh recently attended a class on Prime Numbers. They learnt about a term "Prime Score" which is defined for all N > 1. For a number N = p1a x p2b x p3b ... x pkm where p1,p2,...pk are prime factors of N, Prime Score of N = a+b+...+m. While Mahesh was interested only in primes, Rohil thought how about playing around with Composite Numbers. Both started discussing and found out something known as Perfect Composite Numbers. They defined a Composite number N as Perfect Composite if it is divisible by all the factors of its Prime Score.
Whoa!! That's a nice discovery both of them have made. Now, they are interested in finding the number of Perfect Composites between A and B (inclusive) having Prime Score K. They want you to write a program for the same.

INPUT SPECIFICATIONS

First line contains a single integer T <= 10000, the number of testcases. Each following line contains three integers A, B and K (2 <= A <= B <= 105  and  K >= 0).

OUTPUT SPECIFICATIONS

For each test case, print a single integer - the number of Perfect Composite numbers between A and B (inclusive) having Prime Score = K.

SAMPLE I/O

INPUT :

5
2 5 2
3 100 3
4 10 5
90 456 8
34 67 5

OUTPUT :

1
11
0
2
0


Added by:Mahesh Chandra Sharma
Date:2011-01-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2019-10-15 13:25:19
what do you mean by 'factor' ? Is it divisor or the prime factor of the score k ?
2018-04-18 13:10:25
How the hell did others get AC following statement like this? Perfect composite is divisible by its prime score, not just the "factors" of it. Eg. 100 is a PC with score 4 but 90 is not. AC'd with a desperate guess :/

Other than the broken statement, a legit classical IMHO.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.