Vaishnav and Pizzas

Problem

Idea : Given an integer N . You have to find out the nuber of P/Q where gcd(P,Q) = 1 ,  P/Q<1 and P,Q can be up to N .

To do so , if we iterate P , Q up to N and try to cheak gcd , it must get TLE . Because N can be up to 10000 and the complexity is 10000*10000 will not pass within the given time limit . 

So , we need the help of Euler's Totient Function . You can learn Euler's Totient Function from wiki .
Euler's Totient Function gives the number of integer i(<n) that are co-prime to n . That means their gcd = 1 .

Euler's Totient Function gives output 1 for input 1 . But 1/1 = 1 .So we can avoid this . We can make P/Q by any co-prime/n(<1) . So for every value throw 2 to N returned by Euler's Totient Function is the possible couple of number . We can add these and our answer is this .

My Solution