# http://e...content-available-to-author-only...s.org/index.php?title=Miller-Rabin_primality_test_(Ruby)&diff=16299&oldid=16298
def modPow(x, r, m)
    y = r
    z = x
    v = 1
    while y > 0
        u = y % 2
        t = y / 2
        if u == 1
            v = (v * z) % m
        end
        z = z * z % m
        y = t
    end
    return v
end
 
 
def miller_rabin_pass(a, n)
    d = n - 1
    s = 0
    while d % 2 == 0 do
        d >>= 1
        s += 1
    end
 
 
    a_to_power = modPow(a, d, n)
    if a_to_power == 1
        return true
    end
    for i in 0...s do
        if a_to_power == n - 1
            return true
        end
        a_to_power = (a_to_power * a_to_power) % n
    end
    return (a_to_power == n - 1)
end
 
 
def miller_rabin(n)
    k = 20
    for i in 0...k do
        a = 0
        while a == 0
             a = rand(n)
        end
        if (!miller_rabin_pass(a, n))
            return false
        end
    end
    return true
end
 
s = (2 ** 80).to_s
init = s[0, s.size / 2].to_i
n = init
while n > 0
  9.downto(0).each do |i|
    s = n.to_s
    ss = "#{s}#{i}#{s.reverse}"
    if miller_rabin(ss.to_i)
      puts ss
      exit
    end
  end
  n -= 1
end

IyBodHRwOi8vZS4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4ucy5vcmcvaW5kZXgucGhwP3RpdGxlPU1pbGxlci1SYWJpbl9wcmltYWxpdHlfdGVzdF8oUnVieSkmZGlmZj0xNjI5OSZvbGRpZD0xNjI5OApkZWYgbW9kUG93KHgsIHIsIG0pCiAgICB5ID0gcgogICAgeiA9IHgKICAgIHYgPSAxCiAgICB3aGlsZSB5ID4gMAogICAgICAgIHUgPSB5ICUgMgogICAgICAgIHQgPSB5IC8gMgogICAgICAgIGlmIHUgPT0gMQogICAgICAgICAgICB2ID0gKHYgKiB6KSAlIG0KICAgICAgICBlbmQKICAgICAgICB6ID0geiAqIHogJSBtCiAgICAgICAgeSA9IHQKICAgIGVuZAogICAgcmV0dXJuIHYKZW5kCgoKZGVmIG1pbGxlcl9yYWJpbl9wYXNzKGEsIG4pCiAgICBkID0gbiAtIDEKICAgIHMgPSAwCiAgICB3aGlsZSBkICUgMiA9PSAwIGRvCiAgICAgICAgZCA+Pj0gMQogICAgICAgIHMgKz0gMQogICAgZW5kCgoKICAgIGFfdG9fcG93ZXIgPSBtb2RQb3coYSwgZCwgbikKICAgIGlmIGFfdG9fcG93ZXIgPT0gMQogICAgICAgIHJldHVybiB0cnVlCiAgICBlbmQKICAgIGZvciBpIGluIDAuLi5zIGRvCiAgICAgICAgaWYgYV90b19wb3dlciA9PSBuIC0gMQogICAgICAgICAgICByZXR1cm4gdHJ1ZQogICAgICAgIGVuZAogICAgICAgIGFfdG9fcG93ZXIgPSAoYV90b19wb3dlciAqIGFfdG9fcG93ZXIpICUgbgogICAgZW5kCiAgICByZXR1cm4gKGFfdG9fcG93ZXIgPT0gbiAtIDEpCmVuZAoKCmRlZiBtaWxsZXJfcmFiaW4obikKICAgIGsgPSAyMAogICAgZm9yIGkgaW4gMC4uLmsgZG8KICAgICAgICBhID0gMAogICAgICAgIHdoaWxlIGEgPT0gMAogICAgICAgICAgICAgYSA9IHJhbmQobikKICAgICAgICBlbmQKICAgICAgICBpZiAoIW1pbGxlcl9yYWJpbl9wYXNzKGEsIG4pKQogICAgICAgICAgICByZXR1cm4gZmFsc2UKICAgICAgICBlbmQKICAgIGVuZAogICAgcmV0dXJuIHRydWUKZW5kCgpzID0gKDIgKiogODApLnRvX3MKaW5pdCA9IHNbMCwgcy5zaXplIC8gMl0udG9faQpuID0gaW5pdAp3aGlsZSBuID4gMAogIDkuZG93bnRvKDApLmVhY2ggZG8gfGl8CiAgICBzID0gbi50b19zCiAgICBzcyA9ICIje3N9I3tpfSN7cy5yZXZlcnNlfSIKICAgIGlmIG1pbGxlcl9yYWJpbihzcy50b19pKQogICAgICBwdXRzIHNzCiAgICAgIGV4aXQKICAgIGVuZAogIGVuZAogIG4gLT0gMQplbmQ=