He guys if you can't come up with any formula...pre-computation will do the job.I could not come up with any formula so I used precomputation and AC in 0.015 sec.Good luck :)