8587340257
 9
 81
 27
 1408514752349
 25
 49380563
 266418
 319757451841
 6599669076000
 8
 1000000000000
 30971726
 274875809788
 64
 34280152201
 236
 472670214391
 7938986881993
 44
 4
 388
 2
 802241960524
 3047527844089
 5
 12
 614125
 1716443237161
 48855707
 99
 9999925100701
 5839252225
 3
 50
 1307514188557
 9999926826034
 1468526771489
 2975
 8110708459517
 401120980262
 5138168457911
 1245373417369
 128
 16
 2000000014
 445538663413
 57461344602
 324
 7420738134810

1
9409 2 1
9 1
9 1
72361 2 1
289 1
6 1
289 1
4 1
4 1
4 2 1
4 1
4 2 1
4 1
23020027 1
378028993 1
4 2 1
4 1
0 1
4 2 1
0 1
4 1
25 1
5329 1
2603 1
9 1
0 1
25 1
0 1
10 1
39283 2 1
613783 1
25 2 2 2 1
908209 1
4 1
4 2 1
0 1
6 1
4 1
6
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define endl "\n"
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

unordered_map<ll, int> get_primes(ll n) {
    unordered_map<ll, int> facs;
    ll n2 = n;
    for(ll i = 2; i*i <= n; i++) {
        while (n2 % i == 0) {
            facs[i] += 1;
            n2 /= i;
        }
    }
    if (n2 > 1)
        facs[n2] += 1;
    return facs;
}

vector<ll> get_facs(unordered_map<ll, int>& primes) {
    vector<int> nums, cnt;
    for(auto p: primes) {
        nums.push_back(p.first);
        cnt.push_back(p.second);
    }
    vector<ll> ans;
    auto dfs = [&] (auto self, int d, ll cur) -> void {
        if (d == nums.size()) {
            ans.push_back(cur);
            return;
        }
        ll pre_mul = 1;
        for(int i = 0; i <= cnt[d]; i++) {
            self(self, d+1, cur*pre_mul);
            pre_mul *= nums[d];
        }
    };
    dfs(dfs, 0, 1);
    return ans;
}
bool is_prime(ll n) {
    if( n== 1) return false;
    for(ll i = 2; i*i <= n; i+=1)
        if (n % i == 0)
            return false;
    return true;
}
int main() {
    ll n;
    cin >> n;
    if (is_prime(n) || n == 1) {
        cout << 1 << endl << 0 << endl;
        return 0;
    }
    auto prime = get_primes(n);
    vector<ll> facs = get_facs(prime);
    set<ll> fac2(facs.begin(), facs.end());
    fac2.erase(1);
    vector<ll> arr(fac2.begin(), fac2.end());
    
    unordered_map<ll, int> dp;
    unordered_map<ll, int> ans;
    for(int i = 0; i < arr.size(); i++) {
        if (is_prime(arr[i])) {
            dp[arr[i]] = 1;
            ans[arr[i]] = 0;
            continue;
        }
        int num_fac = 0, cnt_win = 0;
        for(int j = 0; j < i; j++) {            
            if (arr[i] % arr[j] == 0) {
                num_fac += 1;
                if (dp[arr[j]] == 1) {
                    cnt_win += 1;
                } else {
                    ans[arr[i]] = arr[j];
                }
            }            
        }
        if (num_fac == cnt_win) {
            dp[arr[i]] = 0;                
        } else {
            dp[arr[i]] = 1;
        }
    }

    if (dp[n] == 1) {
        cout << 1 << endl;
        cout << ans[n] << endl;
    } else {
        cout << 2 << endl;
    }
    
    return 0;
}
