Finally solved this one. My algorithm takes around 1.5 second for T=10^5.

Hello guys ! Can we use files attached to the solution... Those files will serve as a registry to store commun values like perfect squares bellow 10^12 ... Thanks :)

Guys, for the first time I’m very disappointed. I’ve spent weeks trying to find problem in my solution, but the problem was not there. The problem is that the #141 is incorrectly judged. The solution that is accepted is NOT mathematically correct and is missing whole bunch of numbers.... I think problem setter/tester should urgently revisit the solution and make necessary adjustments! :(

for 2 0 1000000 1 1000000 I got: 700738 5490496

I am having runtime error in testcases though the sample is working fine.Anybody can give me a clue?