1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
#include <unordered_map>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long LL;

namespace mul {
  LL mul(LL a, LL b, LL mod) {
    LL res = 0;
    while (a)
    {
      if (a % 2) {
        res = res + b;
        if (res >= mod) res -= mod;
      }
      a /= 2;
      b = b + b;
      if (b >= mod) b -= mod;
    }
    return res;
  }
};

#define PB push_back

LL MOD;

struct Fmatrix {
  LL m[2][2];
  Fmatrix() {
    m[0][0] = m[0][1] = m[1][0] = 1;
    m[1][1] = 0;
  }
};

Fmatrix operator*(const Fmatrix &lhs, const Fmatrix &rhs) {
  Fmatrix res;
  res.m[0][0] = res.m[0][1] = res.m[1][0] = res.m[1][1] = 0;
  for (int i=0;i<2;i++)
    for (int j=0;j<2;j++)
      for (int k=0;k<2;k++)
        res.m[i][j] = (res.m[i][j] + mul::mul(lhs.m[i][k], rhs.m[k][j], MOD)) % MOD;
  return res;
}

LL fib(LL n, LL mod) {
  MOD = mod;
  if (n < 2) return n;
  n -= 2;
  Fmatrix res = Fmatrix();
  Fmatrix sq = Fmatrix();
  for (;n;n/=2)
  {
    if (n % 2) res = res * sq;
    sq = sq * sq;
  }
  return res.m[0][0];
}

LL period[20];

LL solve(LL n, int len) {
  vector<LL> cand, new_cand;
  LL mod = 10;
  for (int i=0;i<60;i++)
    if (fib(i, 10) == n % 10LL)
      cand.PB(i);

  for (int i=1;i<len;i++)
  {
    mod *= 10LL;
    new_cand.clear();
    for (LL c : cand)
      for (;c<period[i+1];c+=period[i])
        if (fib(c, mod) == n % mod)
          new_cand.PB(c);
    cand.swap(new_cand);
  }
  return cand.empty() ? -1 : cand.back();
}

void init() {
  period[1] = 60;
  period[2] = 300;
  period[3] = 1500;
  for (int i=4;i<20;i++)
    period[i] = period[i-1] * 10LL;
}

int main() {
  init();
  char N[20];
  LL n;
  scanf("%s", N);
  sscanf(N, "%lld", &n);
  LL res = solve(n, strlen(N));
  if (res == -1) printf("NIE\n");
  else printf("%lld\n", res);
  return 0;
}