import Data.List(group, insert)
 
primes = filterPrime [2..] where
  filterPrime (p:xs) = p: filterPrime [x | x <- xs, x `mod` p /= 0]
 
cal = product . zipWith (^) primes
 
count = (`div` 2) . (+1) . product . map ((+1) . (*2))
 
root m = head . dropWhile ((<= m) . count . map (*2)) . iterate (1:) $ []
 
next ns = case (group ns) of
  (x:xs):(y:ys):zs -> concat ((x+1:xs):(y:ys):zs): (if x==y+1 then [concat ((x:xs):(x:ys):zs)] else [])
  (x:xs):_ -> (x+1:xs): (if x==1 then [x:x:xs] else [])
 
solve m = s [] [root m] where
  s ms (ns:nss) = if count ns > m then s (insert (cal ns) ms) nss else s ms (nss ++ next ns)
  s ms _ = head ms
 
main = mapM_ putSolveLn [2,5,10,100,1000,10000,250000000000] where
  putSolveLn n = putStrLn $ show n ++ " -> " ++ (show . solve $ n)

aW1wb3J0IERhdGEuTGlzdChncm91cCwgaW5zZXJ0KQoKcHJpbWVzID0gZmlsdGVyUHJpbWUgWzIuLl0gd2hlcmUKICBmaWx0ZXJQcmltZSAocDp4cykgPSBwOiBmaWx0ZXJQcmltZSBbeCB8IHggPC0geHMsIHggYG1vZGAgcCAvPSAwXQoKY2FsID0gcHJvZHVjdCAuIHppcFdpdGggKF4pIHByaW1lcwoKY291bnQgPSAoYGRpdmAgMikgLiAoKzEpIC4gcHJvZHVjdCAuIG1hcCAoKCsxKSAuICgqMikpCgpyb290IG0gPSBoZWFkIC4gZHJvcFdoaWxlICgoPD0gbSkgLiBjb3VudCAuIG1hcCAoKjIpKSAuIGl0ZXJhdGUgKDE6KSAkIFtdCgpuZXh0IG5zID0gY2FzZSAoZ3JvdXAgbnMpIG9mCiAgKHg6eHMpOih5OnlzKTp6cyAtPiBjb25jYXQgKCh4KzE6eHMpOih5OnlzKTp6cyk6IChpZiB4PT15KzEgdGhlbiBbY29uY2F0ICgoeDp4cyk6KHg6eXMpOnpzKV0gZWxzZSBbXSkKICAoeDp4cyk6XyAtPiAoeCsxOnhzKTogKGlmIHg9PTEgdGhlbiBbeDp4OnhzXSBlbHNlIFtdKQoKc29sdmUgbSA9IHMgW10gW3Jvb3QgbV0gd2hlcmUKICBzIG1zIChuczpuc3MpID0gaWYgY291bnQgbnMgPiBtIHRoZW4gcyAoaW5zZXJ0IChjYWwgbnMpIG1zKSBuc3MgZWxzZSBzIG1zIChuc3MgKysgbmV4dCBucykKICBzIG1zIF8gPSBoZWFkIG1zCgptYWluID0gbWFwTV8gcHV0U29sdmVMbiBbMiw1LDEwLDEwMCwxMDAwLDEwMDAwLDI1MDAwMDAwMDAwMF0gd2hlcmUKICBwdXRTb2x2ZUxuIG4gPSBwdXRTdHJMbiAkIHNob3cgbiArKyAiIC0+ICIgKysgKHNob3cgLiBzb2x2ZSAkIG4p