phi(n) = n * product(1-1/p for all primes p if p|n) therefore: n/phi(n) = product(p/(p-1) for all primes p if p|n)

Since p/(p-1) is larger for smaller values of p, it is reasonable to assume (and it can be proved) that the answer n will always be the largest product of the first r primes such that the product is less than N.

You only need the first 16 primes to reach a product greater than 10^18 so only the first 15 primes (the largest being 53) are needed.

Sieve the primes up to 53. Sort the test inputs N (preserving the order somewhere so you can output them in the correct order) and simply begin multiplying primes until you get past the next N. Store the value previous to the last multiplication and continue untill all N values have theri associated answer.

kitchent asked how we would answer if n/phi would also be needed: as you multiply primes, also multiply p/(p-1) to a seperate variable that stores the n/phi(n) ratio.