you are calling the sieve function again and again for each test case which i was also doing , instead we should precompute the sieve funcn once for n=10^7 and store the values , for the code you can take a look at the above discussions.
can someone say what is wrong in this code. Its only partially correct
Thanks a lot,your solution is great!Learnt something new from it.