#include<iostream>
#include<vector>
#include<math.h>

using namespace std;

bool isPerfectSquare(int x)
{
    int s = sqrt(x);
    return (s * s == x);
}

bool isFibonacci(int n)
{

    return isPerfectSquare(5 * n * n + 4) ||
           isPerfectSquare(5 * n * n - 4);
}

vector <int> relleno (vector <int> v, int i){
    v[i] = v[i - 1] + v[i - 2];
    i++;
    if(i < v.size()) return relleno(v, i);
    else return v;
}

void casos(vector <bool> v, int i, vector <int> fibonacci){
    bool completo = false;
    int k = i;
      for(int j = 0; j < 25; j++){
          if(fibonacci[j] == k || v[i - k]){ v[i] = false; completo = true;}
          else k--;
      }
      if(!completo) v[i] = true;
    if (v.size() < pow(10, 5)) casos(v, i++, fibonacci);
    else return;
}


int main(){
    vector <bool> guanya1 (pow(10, 5));
    int n;
    vector <int> fibonacci (25);
    fibonacci[0] = 1;
    fibonacci[1] = 1;
    relleno(fibonacci, 2);
    guanya1[0] = false;
    guanya1[1] = true;
    casos(guanya1, 2, fibonacci);
    while(cin >> n){
      if (isFibonacci(n)) cout << 1 << endl;
      else if(guanya1[n]) cout << 1 << endl;
      else cout << 2 << endl;
    }
}