use std::cmp::Ordering;
use std::fs;

const BASE: u64 = 1_000_000_000;

#[derive(Clone, Eq, PartialEq)]
struct BigInt {
    digits: Vec<u64>,
}

impl BigInt {
    fn from_str(s: &str) -> Self {
        let mut digits = Vec::new();
        let s = s.trim();
        let mut i = s.len() as i32;
        while i > 0 {
            let start = (i - 9).max(0) as usize;
            let part = &s[start..i as usize];
            digits.push(part.parse::<u64>().unwrap());
            i -= 9;
        }
        while digits.len() > 1 && digits.last() == Some(&0) { digits.pop(); }
        BigInt { digits }
    }

    fn to_string(&self) -> String {
        if self.digits.is_empty() { return "0".to_string(); }
        let mut res = self.digits.last().unwrap().to_string();
        for i in (0..self.digits.len() - 1).rev() {
            res.push_str(&format!("{:09}", self.digits[i]));
        }
        res
    }

    fn multiply(&self, other: &Self) -> Self {
        let mut result = vec![0u128; self.digits.len() + other.digits.len()];
        for (i, &d1) in self.digits.iter().enumerate() {
            for (j, &d2) in other.digits.iter().enumerate() {
                result[i + j] += d1 as u128 * d2 as u128;
                if result[i + j] >= (BASE as u128 * BASE as u128) { // Optimizare carry parțial
                    result[i+j+1] += result[i+j] / BASE as u128;
                    result[i+j] %= BASE as u128;
                }
            }
        }

        let mut final_digits = Vec::new();
        let mut carry = 0u128;
        for val in result {
            let total = val + carry;
            final_digits.push((total % BASE as u128) as u64);
            carry = total / BASE as u128;
        }
        while carry > 0 {
            final_digits.push((carry % BASE as u128) as u64);
            carry /= BASE as u128;
        }
        while final_digits.len() > 1 && final_digits.last() == Some(&0) {
            final_digits.pop();
        }
        BigInt { digits: final_digits }
    }

    fn compare(&self, other: &Self) -> Ordering {
        if self.digits.len() != other.digits.len() {
            return self.digits.len().cmp(&other.digits.len());
        }
        for (d1, d2) in self.digits.iter().rev().zip(other.digits.iter().rev()) {
            if d1 != d2 { return d1.cmp(d2); }
        }
        Ordering::Equal
    }

    fn pow_with_limit(&self, exp: u32, target: &BigInt) -> Ordering {
        if exp == 1 { return self.compare(target); }
        let mut res = BigInt { digits: vec![1] };
        for _ in 0..exp {
            res = res.multiply(self);
            if res.compare(target) == Ordering::Greater { return Ordering::Greater; }
        }
        res.compare(target)
    }
}

fn get_mid(low: &BigInt, high: &BigInt) -> BigInt {
    let mut sum = Vec::new();
    let mut carry = 0u64;
    let n = low.digits.len().max(high.digits.len());
    for i in 0..n {
        let d1 = *low.digits.get(i).unwrap_or(&0);
        let d2 = *high.digits.get(i).unwrap_or(&0);
        let s = d1 as u128 + d2 as u128 + carry as u128;
        sum.push((s % BASE as u128) as u64);
        carry = (s / BASE as u128) as u64;
    }
    if carry > 0 { sum.push(carry); }

    let mut mid = Vec::new();
    let mut rem = 0u128;
    for &d in sum.iter().rev() {
        let val = d as u128 + rem * BASE as u128;
        mid.push((val / 2) as u64);
        rem = val % 2;
    }
    mid.reverse();
    while mid.len() > 1 && mid.last() == Some(&0) { mid.pop(); }
    BigInt { digits: mid }
}

fn add_one(n: &BigInt) -> BigInt {
    let mut digits = n.digits.clone();
    let mut carry = 1;
    for d in &mut digits {
        *d += carry;
        if *d < BASE { carry = 0; break; }
        *d = 0;
        carry = 1;
    }
    if carry > 0 { digits.push(1); }
    BigInt { digits }
}

fn sub_one(n: &BigInt) -> BigInt {
    let mut digits = n.digits.clone();
    for d in &mut digits {
        if *d > 0 { *d -= 1; break; }
        *d = BASE - 1;
    }
    while digits.len() > 1 && digits.last() == Some(&0) { digits.pop(); }
    BigInt { digits }
}

fn main() -> std::io::Result<()> {
    let p_str = fs::read_to_string("numere2.in")?.trim().to_string();
    let p = BigInt::from_str(&p_str);
    for b in (1..=335).rev() {
        if b == 1 {
            fs::write("numere2.out", format!("{}\n1\n", p_str))?;
            return Ok(());
        }
        let mut low = BigInt { digits: vec![2] };
        let mut high = BigInt::from_str(&"9".repeat((p_str.len() / b as usize) + 1));
        while low.compare(&high) != Ordering::Greater {
            let mid = get_mid(&low, &high);
            if mid.digits.is_empty() || (mid.digits.len() == 1 && mid.digits[0] < 2) {
                low = add_one(&mid);
                continue;
            }
            match mid.pow_with_limit(b, &p) {
                Ordering::Equal => {
                    fs::write("numere2.out", format!("{}\n{}\n", mid.to_string(), b))?;
                    return Ok(());
                },
                Ordering::Less => low = add_one(&mid),
                Ordering::Greater => high = sub_one(&mid),
            }
        }
    }
    Ok(())
}