EULER TOTIENT: approach for TIMUS 1673

I encountered this

http://acm.timus.ru/problem.aspx?space=1&num=1673

problem some time ago…i know it can be done by use of euler totient.

Can somebody explain how to solve it?

//