EULER TOTIENT: approach for TIMUS 1673

general
, , , ,
1

I encountered this

1673. Admission to Exam @ Timus Online Judge

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

Can somebody explain how to solve it?