It is showing TLE in one of the test case
hey ayush,
Your code is giving is TLE because you are expected to answer each query in O(1).
You have generated the primes in most optimized manner, just try to pre compute for each number outside the test cases loop and then answer it in O(1).
Please let me know if there is any other doubt.