Zeroes VII

All submissions for this problem are available.
Factorial n or n! is defined as below:
n! = 1*2*3*...*n
For example 7! = 1*2*3*4*5*6*7 = 5040. Now, if we prime factorize a factorial we will be able to find the frequency of each prime in it For example 7!= 5040 = 2^{4}*3^{2}*5*7. So there are exactly four 2's, two 3's, one 5 and one 7 in 7!. For factorials of large numbers primefactorization is not a good idea and there are many better ways to find out frequency of prime numbers it factorials of large number. Now consider 15 numbers 1!, 2!, 3!, 4!, 5!, 6!, 7!, 8!, 9!, 10!, 11!, 12!, 13!, 14!, 15! and a set of consecutive prime numbers {3, 5, 7, 11, 13} (2nd, 3rd, 4th, 5th and 6th) and an integer 2 (The frequency) and you are asked to find how many of these numbers have one prime from the set of primes exactly two times. The answer will be 9 and these 9 numbers are shown below:
Value  Primes that are present exactly 2 times 
6!  3 
7!  3 
8!  3 
10!  5 
11!  5 
12!  5 
13!  5 
14!  5, 7 
15!  7 
In this problem you are asked to solve a generalized version of this problem. Given a set of factorials of consecutive numbers F, a set of consecutive prime numbers P and an integer t, you job is two find out how many of the numbers in F contains any one of the prime numbers from set P exactly t times. But if more than one prime from P is present exactly t times in some number, it is ok.
Input
The first line contains a positive integer C (0<C<51) which denotes the total number of test cases to follow. Each of the next C lines consists input for a single test case. Each line contains five positive integers low, high (0 < low < high ≤ 2*10^{16}), plow, phigh (0 < plow < phigh ≤ 3000000) and t (0 < t ≤ 300000). These numbers denotes that you have to deal with the set of factorial of consecutive numbers low!, (low+1)!, (low+2)! ..., (high1)!, high! and a set of primes P which contains P_{plow}, P_{plow+1}, ..., P_{phigh}. Primes are numbered starting from 1, so P_{1} is actually 2, P_{2}=3, P_{3}=5, P_{4}=7, P_{5}=11 etc. You will have to find how many of these factorials contains one or more primes from this set P exactly t times.Output
For each test case produce one line of output. This line contains at integer M, which denotes how many of the numbers low!, (low+1)!, (low+2)! ..., (high1)!, high! contains at least one prime from set P exactly t times.
Sample
Input 2 10 20 1 5 3 10 20 1 5 6 Output 5 3
Author:  kol_adm 
Editorial  https://discuss.codechef.com/problems/KOL16C 
Tags  acm16kol, binarysearch, hard, kol_adm 
Date Added:  21122016 
Time Limit:  6 sec 
Source Limit:  40000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 