/*
    Author : quickn (quickn.ga)
    Email  : quickwshell@gmail.com
*/

use std::cmp::min;
use std::str;
use std::io::{self, BufWriter, Write};

/// Same API as Scanner but nearly twice as fast, using horribly unsafe dark arts
/// **REQUIRES** Rust 1.34 or higher
pub struct UnsafeScanner<R> {
    reader: R,
    buf_str: Vec<u8>,
    buf_iter: str::SplitAsciiWhitespace<'static>,
}

impl<R: io::BufRead> UnsafeScanner<R> {
    pub fn new(reader: R) -> Self {
        Self {
            reader,
            buf_str: Vec::new(),
            buf_iter: "".split_ascii_whitespace(),
        }
    }

    /// This function should be marked unsafe, but noone has time for that in a
    /// programming contest. Use at your own risk!
    pub fn token<T: str::FromStr>(&mut self) -> T {
        loop {
            if let Some(token) = self.buf_iter.next() {
                return token.parse().ok().expect("Failed parse");
            }
            self.buf_str.clear();
            self.reader
                .read_until(b'\n', &mut self.buf_str)
                .expect("Failed read");
            self.buf_iter = unsafe {
                let slice = str::from_utf8_unchecked(&self.buf_str);
                std::mem::transmute(slice.split_ascii_whitespace())
            }
        }
    }
}

use std::mem::MaybeUninit;
use std::collections::HashMap;

//const MAX: usize = 20912792;

/*fn atkin_sieve(d: usize) -> Vec<u32> {
    let mut is_composite: Vec<bool> = Vec::with_capacity(d+1);
    let mut primes: Vec<u32> = Vec::new();
    is_composite.resize(d+1, false);
    let sqrt_d = (d as f64).sqrt().floor() as usize;
    let s1 = [1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59];
    let s2 = [1,13,17,29,37,41,49,53];
    let s3 = [7,19,31,43];
    let s4 = [11,23,47,59];
    for w in 0..=(d/60) {
        for x in s1.iter().take_while(|&&l| 60*w + l <= d) {
            let idx = 60*w + x;
            is_composite[idx] = true;
        }
    }
    for x in 1..=(sqrt_d>>1) {
        let r1 = (x*x)<<2;
        if r1 > d { break; }
        for y in (0..=(sqrt_d>>1)).map(|k| (k<<1)+1).collect::<Vec<usize>>().iter().take_while(|&&l| r1+(l*l) <= d) {
            let idx = r1+(y*y);
            if idx > d { break; }
            if s2.binary_search(&(idx%60)).is_ok() {
                is_composite[idx] = !is_composite[idx];
            }
        }
    }
    for x in (0..=(sqrt_d>>1)).map(|k| (k<<1)+1) {
        let r1 = (x*x)*3;
        if r1 > d { break; }
        for y in (1..=(sqrt_d>>1)).map(|k| k<<1).collect::<Vec<usize>>().iter().take_while(|&&l| r1+(l*l) <= d) {
            let idx = r1+(y*y);
            if idx > d { break; }
            if s3.binary_search(&(idx%60)).is_ok() {
                is_composite[idx] = !is_composite[idx];
            }
        }
    }
    for x in 2..=sqrt_d {
        let r1 = (x*x)*3;
        if r1 > d { break; }
        let mut y = x-1;
        loop {
            let idx = r1-(y*y);
            if s4.binary_search(&(idx%60)).is_ok() {
                is_composite[idx] = !is_composite[idx];
            }
            if y <= 2 { break; }
            y -= 2;
        }
    }
    for w in 0..=sqrt_d {
        let r1 = 60*w;
        if r1 > sqrt_d { break; }
        for x in s1.iter() {
            let idx = r1 + x;
            if idx >= 7 {
                if idx > sqrt_d { break; }
                if !is_composite[idx] {
                    for w_p in 0..=d {
                        if w_p*idx*idx > d { break; }
                        for x_p in s1.iter() {
                            let idx2 = 60*w_p + x_p;
                            let c = idx2*idx*idx;
                            if c > d { break; }
                            is_composite[c] = true;
                        }
                    }
                }
            }
        }
    }
    primes.append(&mut [2, 3, 5].to_vec());
    for w in 0..=(d/60) {
        for x in s1.iter() {
            let idx = 60*w + x;
            if idx > d { break; }
            if idx >= 7 && !is_composite[idx] {
                primes.push(idx as u32);
            }
        }
    }
    primes
}*/

use std::time::{Duration, SystemTime};
use std::thread;

fn main() {
    let (stdin, stdout) = (io::stdin(), io::stdout());
    let mut scan = UnsafeScanner::new(stdin.lock());
    let mut sout = BufWriter::new(stdout.lock());
    let n: usize = scan.token::<usize>();
    let now = SystemTime::now();
    let d: usize = ((n<<1) as f64).powf(0.2).floor().powi(2) as usize;
    let sqrt_d = (d as f64).sqrt().floor() as usize;
    let mut mu: Box<[i8]> = vec![1;d+1].into_boxed_slice();
    let mut m: Box<[u32]> = vec![1;d+1].into_boxed_slice();
    let mut s_mu: Box<[i32]> = vec![0;d+1].into_boxed_slice();
    let mut is_composite: Box<[bool]> = vec![false;sqrt_d+1].into_boxed_slice();
    let mut primes: Vec<u32> = Vec::new();
    for p in 2..=sqrt_d {
        if !is_composite[p] { primes.push(p as u32); }
        for j in 0..primes.len() {
            let q = primes[j];
            let v = (q as usize)*p;
            if v > sqrt_d { break; }
            is_composite[v] = true;
            if p % (q as usize) == 0 { break; }
        }
    }
    mu[0] = 0;
    m[0] = 0;
    s_mu[1] = 1;
    for i in 0..primes.len() {
        let p = primes[i];
        let p_pow = (p*p) as usize;
        for k in 1..=d/p_pow {
            mu[k*p_pow] = 0;
        }
        for k in 1..=d/(p as usize) {
            let idx = k*(p as usize);
            mu[idx] *= -1;
            if (m[idx] as u64)*(p as u64) > (d as u64) {
                m[idx] = (d as u32)+1;
            } else {
                m[idx] *= p;
            }
        }
    }
    for k in 1..=d {
        if m[k] < (k as u32) {
            mu[k] *= -1;
        }
    }
    for p in 2..=d {
        s_mu[p] = s_mu[p-1] + (mu[p] as i32);
    }
    let mut hash_s_mu: HashMap<usize, i64> = HashMap::new();
    let mut f_mu = unsafe { MaybeUninit::zeroed().assume_init() };
    let rec_f_mu = &mut f_mu as *mut dyn FnMut(usize) -> i64;
    f_mu = |m: usize| -> i64 {
        if m <= d {
            s_mu[m] as i64
        } else {
            if let Some(&res) = hash_s_mu.get(&m) {
                res
            } else {
                let mut res = 1;
                let mut i = m;
                while i > 1 {
                    let f = m/i;
                    let next_i = m/(f+1);
                    res -= unsafe { ((i-next_i) as i64)*(*rec_f_mu)(f) };
                    i = next_i;
                }
                hash_s_mu.insert(m, res);
                res
            }
        }
    };
    let mu_cp = mu.clone();
    let mut hash_f: HashMap<usize, usize> = HashMap::new();
    let mut f = |m: usize| -> usize {
        if let Some(&res) = hash_f.get(&m) {
            res
        } else {
            //let new_d = (m as f64).powf(0.2).floor().powi(2) as usize;
            let mut i = (m as f64).sqrt().floor() as usize;
            let mut res = 0;
            while i > d {
                let f = m/(i*i);
                let next_i = ((m/(f+1)) as f64).sqrt().floor() as usize;
                res += (f_mu(i) - f_mu(next_i))*(f as i64);
                i = next_i;
            }
            let block = i>>2;
            let (s1, s2, s3, s4) = (1, block, block*2, block*3, i);
            let v1 = thread::spawn(move || {
                let r = 0;
                for j in s1..s2 {
                    let f = m/(j*j);
                    r += (mu_cp[j] as i64)*(f as i64);
                }
            });
            let v2 = thread::spawn(move || {
                let r = 0;
                for j in s2..=s2 {
                    let f = m/(j*j);
                    r += (mu_cp[j] as i64)*(f as i64);
                }
            });
            hash_f.insert(m, res as usize);
            res as usize
        }
    };
    let (mut l, mut r) = (n, min(n<<2, 1644934066848209910));
    while f(l) != f(r) && n >= f(l) && n <= f(r) {
        //println!("{} {}", l, r);
        let mid = l + ((((n - f(l)) as u128)*((r - l) as u128)) / ((f(r) - f(l)) as u128)) as usize;
        let func = f(mid);
        if func < n {
            l = mid + 1;
        } else if func > n {
            r = mid - 1;
        } else {
            l = mid;
            break;
        }
    }
    while f(l-1) == f(l) { l -= 1; }
    println!("{:?}", now.elapsed().unwrap());
    writeln!(sout, "{}", l).ok();
    //writeln!(sout, "{} {} {} {}", l, f(3), f(4), f(5)).ok();
}