#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
using namespace std;
int main(){
	long long n;
	cin >> n;
	long long k=0;
	long long j=n/2;
	if ( sqrt ( double ( n ) ) == int ( sqrt ( double ( n ) ) ) ) {
		cout << '1';
		return 0;
	}
	for (i=0;k<j;i++)
	{
		k += 2 * i + 1;
		if ( sqrt ( double ( n-k ) ) == int ( sqrt ( double ( n-k ) ) ) ) {
			cout << '2';
			return 0;
		}
	}
	while ( n % 4 == 0) n /= 4;
	if (n % 8 == 7) cout << '4';
	else cout << '3';
	return 0;
}