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