Idea at a glance: I precalculated all the sum of phi() values till some range. Then while for some query I ran a binary search on the precalculated sum of the euler values.... So according to this process complexity should be O(n) + T*(log(n)
Problem:
https://algo.codemarshal.org/contests/icpc-dhaka-19-preli/problems/G
My code: