This problem was really hard. The algorithm must O(rlogr) to pass all test cases. For me it involved counting coprimes in given range using inclusion/exclusion principle and generating totient values via sieve.

For a head-start in this question watch this video: https://youtu.be/NaL_Cb42WyY

NoSpoilers

For r = 10^7
No. of triangles = 1291928194907737851997176407604203162800560

I'm confused, if there are only integer coordinates, how do r = 2 and r = 3 give different results? Am I missing something?

this stack can be usefull

(https://stackoverflow.com/questions/27713046/number-of-triangles-containing-the-point-0-0)