{-# OPTIONS_GHC -O2 #-}
module Main where
 
main = interact (\s-> show $ primes() !! (read s - 1))
 
primes :: () -> [Int]
primes () = 2: primes'   -- TREE-folding multiples-union
 where                   --  ERATOSthenes sieve
   primes'  = 3: sieve primes' 5 9 []
   sieve (p:ps) x q fs = 
        ([x,x+2..q-2] `minus` 
                          foldt [[y+s,y+2*s..q] | (s,y) <- fs])
        ++ sieve ps (q+2) (head ps^2)
             ((++ [(2*p,q)]) [(s,q-rem (q-y) s) | (s,y) <- fs])
 
   foldt (a:xs)     = union a (foldt (pairs xs)) 
   foldt []         = []
   pairs (a:b:xs)   = union a b : pairs xs
   pairs xs         = xs
 
   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
 
{-                           FOLDT            (w/ foldr)        (w/ foldl)
   100,000:  1,299,709   0.23s    6.8MB      0.40s   7.8MB      1.33s  8.8MB
   0.5 mln:  7,368,787   1.54s   25.2MB      3.80s  31.3MB    300k:7.35s 19MB
   1.0 mln: 15,485,863   3.65s   48.8MB     10.31s  57.0MB    450k:14.1s 28MB
   2.0 mln: 32,452,843   8.74s  110.2MB  
   2.5 mln: 41,161,739  12.02s  134.8MB
 
                     O(n^1.28)  O(n^1.1)   (n^1.41) (n^1.3)   (n^1.57) (^2.1)
-}

ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0KbW9kdWxlIE1haW4gd2hlcmUKCm1haW4gPSBpbnRlcmFjdCAoXHMtPiBzaG93ICQgcHJpbWVzKCkgISEgKHJlYWQgcyAtIDEpKQoKcHJpbWVzIDo6ICgpIC0+IFtJbnRdCnByaW1lcyAoKSA9IDI6IHByaW1lcycgICAtLSBUUkVFLWZvbGRpbmcgbXVsdGlwbGVzLXVuaW9uCiB3aGVyZSAgICAgICAgICAgICAgICAgICAtLSAgRVJBVE9TdGhlbmVzIHNpZXZlCiAgIHByaW1lcycgID0gMzogc2lldmUgcHJpbWVzJyA1IDkgW10KICAgc2lldmUgKHA6cHMpIHggcSBmcyA9IAogICAgICAgIChbeCx4KzIuLnEtMl0gYG1pbnVzYCAKICAgICAgICAgICAgICAgICAgICAgICAgICBmb2xkdCBbW3krcyx5KzIqcy4ucV0gfCAocyx5KSA8LSBmc10pCiAgICAgICAgKysgc2lldmUgcHMgKHErMikgKGhlYWQgcHNeMikKICAgICAgICAgICAgICgoKysgWygyKnAscSldKSBbKHMscS1yZW0gKHEteSkgcykgfCAocyx5KSA8LSBmc10pCiAgICAKICAgZm9sZHQgKGE6eHMpICAgICA9IHVuaW9uIGEgKGZvbGR0IChwYWlycyB4cykpIAogICBmb2xkdCBbXSAgICAgICAgID0gW10KICAgcGFpcnMgKGE6Yjp4cykgICA9IHVuaW9uIGEgYiA6IHBhaXJzIHhzCiAgIHBhaXJzIHhzICAgICAgICAgPSB4cwogICAKICAgdW5pb24gYUAoeDp4cykgYkAoeTp5cykgPSBjYXNlIGNvbXBhcmUgeCB5IG9mIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgTFQgLT4geCA6IHVuaW9uIHhzIGIgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBFUSAtPiB4IDogdW5pb24geHMgeXMKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEdUIC0+IHkgOiB1bmlvbiBhICB5cwogICB1bmlvbiBhICAgICAgICBbXSAgICAgICA9IGEKICAgdW5pb24gW10gICAgICAgYiAgICAgICAgPSBiCiAgIAogICBtaW51cyBhQCh4OnhzKSBiQCh5OnlzKSA9IGNhc2UgY29tcGFyZSB4IHkgb2YgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBMVCAtPiB4IDogbWludXMgeHMgYgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgRVEgLT4gICAgIG1pbnVzIHhzIHlzCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBHVCAtPiAgICAgbWludXMgYSAgeXMKICAgbWludXMgYSAgICAgICAgYiAgICAgICAgPSBhCiAgIAp7LSAgICAgICAgICAgICAgICAgICAgICAgICAgIEZPTERUICAgICAgICAgICAgKHcvIGZvbGRyKSAgICAgICAgKHcvIGZvbGRsKQogICAxMDAsMDAwOiAgMSwyOTksNzA5ICAgMC4yM3MgICAgNi44TUIgICAgICAwLjQwcyAgIDcuOE1CICAgICAgMS4zM3MgIDguOE1CCiAgIDAuNSBtbG46ICA3LDM2OCw3ODcgICAxLjU0cyAgIDI1LjJNQiAgICAgIDMuODBzICAzMS4zTUIgICAgMzAwazo3LjM1cyAxOU1CCiAgIDEuMCBtbG46IDE1LDQ4NSw4NjMgICAzLjY1cyAgIDQ4LjhNQiAgICAgMTAuMzFzICA1Ny4wTUIgICAgNDUwazoxNC4xcyAyOE1CCiAgIDIuMCBtbG46IDMyLDQ1Miw4NDMgICA4Ljc0cyAgMTEwLjJNQiAgCiAgIDIuNSBtbG46IDQxLDE2MSw3MzkgIDEyLjAycyAgMTM0LjhNQgogICAKICAgICAgICAgICAgICAgICAgICAgTyhuXjEuMjgpICBPKG5eMS4xKSAgIChuXjEuNDEpIChuXjEuMykgICAobl4xLjU3KSAoXjIuMSkKLX0=

MTAwMDAwMA==

1000000