#!ruby -nrprime
eval"p (2...n=%d).select{|i|n.gcd(i).prime_division.sum{_2}>=%d}.max_by{|i|i.prime_division.reduce(1){_1*-~_2[1]}}"%$_.split