851.cpp

#include <iostream>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

typedef vector<int> vi;
typedef long long int lli;

int main(){

    bool b1 = true, b2 = true;
    int n, s1, s2;
    cin >> n;
    for (int i = 1; i <= min(5, n); i++){
        for (int j = 1; j <= min(5, n - i); j++){
            // cout << i << " " << j << " : " << endl;
            b2 = true;
            s1 = i;
            s2 = j;
            // cout << s1 << " " << s2 << endl;
            while (s1 + s2 <= n){
                s1 += s2;
                if (s1 + s2 > n)
                    b2 = false;
                s2 += s1;
                // cout << s1 << " " << s2 << endl;
            }
            // cout << b2 << endl;
            if (b2)
                break;
        }
        if (!b2)
            break;
    }
    if (b2)
        cout << 2 << endl;
    else
        cout << 1 << endl;

    return 0;
}