{-# OPTIONS_GHC -O2 #-}
module Main where
 
main = interact (\s-> show $ primes() !! (read s - 1))
 
primes :: () -> [Int]
primes () = 2: primes'   -- LINEAR-folding multiples-union 
 where                   --  ERATOSthenes sieve
   primes'  = 3: sieve primes' 3 []
   sieve (p:ps) x fs = 
     let 
         q=p*p 
     in
        ([x+2,x+4..q-2] `minus` 
            foldl union [] [[y+s,y+2*s..q] | (s,y) <- fs])
        ++ sieve ps q 
               ((2*p,q):[(s,q-rem (q-y) s) | (s,y) <- fs])
 
   union a@(x:xs) b@(y:ys) = case compare x y of 
                                  LT -> x : union xs b 
                                  EQ -> x : union xs ys
                                  GT -> y : union a  ys
   union a        []       = a
   union []       b        = b
 
   minus a@(x:xs) b@(y:ys) = case compare x y of 
                                  LT -> x : minus xs b
                                  EQ ->     minus xs ys
                                  GT ->     minus a  ys
   minus a        b        = a
 
{-
                            FOLDL             FOLDR 
    50,000:    611,953   0.15s  5.8MB      0.44s   5.8MB
   100,000:  1,299,709   0.41s  7.8MB      1.28s   8.8MB
   200,000:  2,750,159   1.09s 14.0MB      3.83s  14.0MB
   300,000:  4,256,233   1.93s 19.1MB      7.08s  19.1MB
   400,000:  5,800,079   2.95s 25.2MB     11.08s  24.2MB 
   500,000:  7,368,787   3.94s 28.2MB   > 15 sec >30.4MB
 1,000,000: 15,485,863  10.93s 58.0MB   > 15 sec >30.4MB
 
                     O(n^1.45) O(n^0.9)
-}

ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0KbW9kdWxlIE1haW4gd2hlcmUKCm1haW4gPSBpbnRlcmFjdCAoXHMtPiBzaG93ICQgcHJpbWVzKCkgISEgKHJlYWQgcyAtIDEpKQoKcHJpbWVzIDo6ICgpIC0+IFtJbnRdCnByaW1lcyAoKSA9IDI6IHByaW1lcycgICAtLSBMSU5FQVItZm9sZGluZyBtdWx0aXBsZXMtdW5pb24gCiB3aGVyZSAgICAgICAgICAgICAgICAgICAtLSAgRVJBVE9TdGhlbmVzIHNpZXZlCiAgIHByaW1lcycgID0gMzogc2lldmUgcHJpbWVzJyAzIFtdCiAgIHNpZXZlIChwOnBzKSB4IGZzID0gCiAgICAgbGV0IAogICAgICAgICBxPXAqcCAKICAgICBpbgogICAgICAgIChbeCsyLHgrNC4ucS0yXSBgbWludXNgIAogICAgICAgICAgICBmb2xkbCB1bmlvbiBbXSBbW3krcyx5KzIqcy4ucV0gfCAocyx5KSA8LSBmc10pCiAgICAgICAgKysgc2lldmUgcHMgcSAKICAgICAgICAgICAgICAgKCgyKnAscSk6WyhzLHEtcmVtIChxLXkpIHMpIHwgKHMseSkgPC0gZnNdKQoKICAgdW5pb24gYUAoeDp4cykgYkAoeTp5cykgPSBjYXNlIGNvbXBhcmUgeCB5IG9mIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgTFQgLT4geCA6IHVuaW9uIHhzIGIgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBFUSAtPiB4IDogdW5pb24geHMgeXMKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEdUIC0+IHkgOiB1bmlvbiBhICB5cwogICB1bmlvbiBhICAgICAgICBbXSAgICAgICA9IGEKICAgdW5pb24gW10gICAgICAgYiAgICAgICAgPSBiCiAKICAgbWludXMgYUAoeDp4cykgYkAoeTp5cykgPSBjYXNlIGNvbXBhcmUgeCB5IG9mIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgTFQgLT4geCA6IG1pbnVzIHhzIGIKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEVRIC0+ICAgICBtaW51cyB4cyB5cwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgR1QgLT4gICAgIG1pbnVzIGEgIHlzCiAgIG1pbnVzIGEgICAgICAgIGIgICAgICAgID0gYQoKey0KICAgICAgICAgICAgICAgICAgICAgICAgICAgIEZPTERMICAgICAgICAgICAgIEZPTERSIAogICAgNTAsMDAwOiAgICA2MTEsOTUzICAgMC4xNXMgIDUuOE1CICAgICAgMC40NHMgICA1LjhNQgogICAxMDAsMDAwOiAgMSwyOTksNzA5ICAgMC40MXMgIDcuOE1CICAgICAgMS4yOHMgICA4LjhNQgogICAyMDAsMDAwOiAgMiw3NTAsMTU5ICAgMS4wOXMgMTQuME1CICAgICAgMy44M3MgIDE0LjBNQgogICAzMDAsMDAwOiAgNCwyNTYsMjMzICAgMS45M3MgMTkuMU1CICAgICAgNy4wOHMgIDE5LjFNQgogICA0MDAsMDAwOiAgNSw4MDAsMDc5ICAgMi45NXMgMjUuMk1CICAgICAxMS4wOHMgIDI0LjJNQiAKICAgNTAwLDAwMDogIDcsMzY4LDc4NyAgIDMuOTRzIDI4LjJNQiAgID4gMTUgc2VjID4zMC40TUIKIDEsMDAwLDAwMDogMTUsNDg1LDg2MyAgMTAuOTNzIDU4LjBNQiAgID4gMTUgc2VjID4zMC40TUIKCiAgICAgICAgICAgICAgICAgICAgIE8obl4xLjQ1KSBPKG5eMC45KQotfQ==

MTAwMDAwMA==

1000000