#include <iostream>
#include <cassert>
 
int64_t euclid(int64_t a, int64_t b) {
  if (b == 0) return a;
  return euclid(b, a % b);
}
 
class Ratio {
  int64_t a;
  int64_t b;
public:
  Ratio() : a(0), b(0) {}
  Ratio(int64_t x, int64_t y) : a(x), b(y) {}
  friend std::ostream &operator<<(std::ostream &s, Ratio r) {
    if (r.b == 1)
      s << r.a;
    else
      s << "(" << r.a << "/" << r.b << ")";
    return s;
  }
  friend Ratio operator+(Ratio const &x, Ratio const &y) {
    Ratio r;
    int64_t c = euclid(x.b, y.b);
    int64_t zy = x.b / c;
    int64_t zx = y.b / c;
    r.b = y.b * zy;
    assert(r.b == x.b * zx);
    r.a = x.a * zx + y.a * zy;
    c = euclid(r.a, r.b);
    r.a = r.a / c;
    r.b = r.b / c;
    return r;
  }
  friend Ratio operator-(Ratio const &x, Ratio const &y) {
    Ratio r;
    int64_t c = euclid(x.b, y.b);
    int64_t zy = x.b / c;
    int64_t zx = y.b / c;
    r.b = y.b * zy;
    assert(r.b == x.b * zx);
    r.a = x.a * zx - y.a * zy;
    c = euclid(r.a, r.b);
    r.a = r.a / c;
    r.b = r.b / c;
    return r;
  }
  friend Ratio operator*(Ratio const &x, Ratio const &y) {
    Ratio r;
    int64_t xa, xb, ya, yb;
    int64_t c1 = euclid(x.a, y.b);
    int64_t c2 = euclid(x.b, y.a);
    xa = x.a / c1; yb = y.b / c1; 
    xb = x.b / c2; ya = y.a / c2; 
    r.a = xa * ya;
    r.b = xb * yb;
    return r;
  }
};
 
class Field5 {
  Ratio a;
  Ratio b;
public:
  Field5() : a(Ratio()), b(Ratio()) {}
  Field5(Ratio x, Ratio y) : a(x), b(y) {}
  friend std::ostream &operator<<(std::ostream &s, Field5 r) {
//    s << "(" << r.a << "," << r.b << ")";
    s << r.b;
    return s;
  }
  friend Field5 operator-(Field5 const &x, Field5 const &y) {
    Field5 r;
    r.a = x.a - y.a; r.b = x.b - y.b;
    return r;
  }
  friend Field5 operator*(Field5 const &x, Field5 const &y) {
    Field5 r;
    r.a = x.a * y.a + Ratio(5, 1) * x.b * y.b;
    r.b = x.a * y.b + x.b * y.a;
    return r;
  }  
};
 
int64_t fib(int n) {
  static int64_t t1 = 1, t2 = 1;
  if (n == 1 || n == 2)
    return 1;
  int64_t s = t1 + t2;
  t1 = t2; t2 = s;
  return s;
}
 
Field5 Field5Power(Field5 a, int n) { /* =a^n */
  unsigned int mask = 1 << (sizeof(int) * 8 - 1);
  Field5 r(Ratio(1, 1), Ratio(0, 1));
  for (;;) {
    if ((n & mask) > 0)
      r = r * a;
    mask = (mask >> 1);
    /* out of loop */
    if (mask == 0)
      break;
    r = r * r;
  }
  return r;
}
 
int const N = 93;
int main() {
  Field5 phi1(Ratio(1, 2), Ratio(1, 2));
  Field5 phi2(Ratio(1, 2), Ratio(-1, 2));
 
  for (int n = 1; n <= N; n++) {
    int64_t s = fib(n);
 
    Field5 r1, r2, r3;
    r1 = Field5Power(phi1, n);
    r2 = Field5Power(phi2, n);
    r3 = r1 - r2;
 
    std::cout << n << ":: " << s << " : " << r3 << std::endl;
  }
  return 0;
}
/* end */
//7540113804746346429
//9223372036854775807
 
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y2Fzc2VydD4KCmludDY0X3QgZXVjbGlkKGludDY0X3QgYSwgaW50NjRfdCBiKSB7CiAgaWYgKGIgPT0gMCkgcmV0dXJuIGE7CiAgcmV0dXJuIGV1Y2xpZChiLCBhICUgYik7Cn0KCmNsYXNzIFJhdGlvIHsKICBpbnQ2NF90IGE7CiAgaW50NjRfdCBiOwpwdWJsaWM6CiAgUmF0aW8oKSA6IGEoMCksIGIoMCkge30KICBSYXRpbyhpbnQ2NF90IHgsIGludDY0X3QgeSkgOiBhKHgpLCBiKHkpIHt9CiAgZnJpZW5kIHN0ZDo6b3N0cmVhbSAmb3BlcmF0b3I8PChzdGQ6Om9zdHJlYW0gJnMsIFJhdGlvIHIpIHsKICAgIGlmIChyLmIgPT0gMSkKICAgICAgcyA8PCByLmE7CiAgICBlbHNlCiAgICAgIHMgPDwgIigiIDw8IHIuYSA8PCAiLyIgPDwgci5iIDw8ICIpIjsKICAgIHJldHVybiBzOwogIH0KICBmcmllbmQgUmF0aW8gb3BlcmF0b3IrKFJhdGlvIGNvbnN0ICZ4LCBSYXRpbyBjb25zdCAmeSkgewogICAgUmF0aW8gcjsKICAgIGludDY0X3QgYyA9IGV1Y2xpZCh4LmIsIHkuYik7CiAgICBpbnQ2NF90IHp5ID0geC5iIC8gYzsKICAgIGludDY0X3QgenggPSB5LmIgLyBjOwogICAgci5iID0geS5iICogenk7CiAgICBhc3NlcnQoci5iID09IHguYiAqIHp4KTsKICAgIHIuYSA9IHguYSAqIHp4ICsgeS5hICogenk7CiAgICBjID0gZXVjbGlkKHIuYSwgci5iKTsKICAgIHIuYSA9IHIuYSAvIGM7CiAgICByLmIgPSByLmIgLyBjOwogICAgcmV0dXJuIHI7CiAgfQogIGZyaWVuZCBSYXRpbyBvcGVyYXRvci0oUmF0aW8gY29uc3QgJngsIFJhdGlvIGNvbnN0ICZ5KSB7CiAgICBSYXRpbyByOwogICAgaW50NjRfdCBjID0gZXVjbGlkKHguYiwgeS5iKTsKICAgIGludDY0X3QgenkgPSB4LmIgLyBjOwogICAgaW50NjRfdCB6eCA9IHkuYiAvIGM7CiAgICByLmIgPSB5LmIgKiB6eTsKICAgIGFzc2VydChyLmIgPT0geC5iICogengpOwogICAgci5hID0geC5hICogenggLSB5LmEgKiB6eTsKICAgIGMgPSBldWNsaWQoci5hLCByLmIpOwogICAgci5hID0gci5hIC8gYzsKICAgIHIuYiA9IHIuYiAvIGM7CiAgICByZXR1cm4gcjsKICB9CiAgZnJpZW5kIFJhdGlvIG9wZXJhdG9yKihSYXRpbyBjb25zdCAmeCwgUmF0aW8gY29uc3QgJnkpIHsKICAgIFJhdGlvIHI7CiAgICBpbnQ2NF90IHhhLCB4YiwgeWEsIHliOwogICAgaW50NjRfdCBjMSA9IGV1Y2xpZCh4LmEsIHkuYik7CiAgICBpbnQ2NF90IGMyID0gZXVjbGlkKHguYiwgeS5hKTsKICAgIHhhID0geC5hIC8gYzE7IHliID0geS5iIC8gYzE7IAogICAgeGIgPSB4LmIgLyBjMjsgeWEgPSB5LmEgLyBjMjsgCiAgICByLmEgPSB4YSAqIHlhOwogICAgci5iID0geGIgKiB5YjsKICAgIHJldHVybiByOwogIH0KfTsKCmNsYXNzIEZpZWxkNSB7CiAgUmF0aW8gYTsKICBSYXRpbyBiOwpwdWJsaWM6CiAgRmllbGQ1KCkgOiBhKFJhdGlvKCkpLCBiKFJhdGlvKCkpIHt9CiAgRmllbGQ1KFJhdGlvIHgsIFJhdGlvIHkpIDogYSh4KSwgYih5KSB7fQogIGZyaWVuZCBzdGQ6Om9zdHJlYW0gJm9wZXJhdG9yPDwoc3RkOjpvc3RyZWFtICZzLCBGaWVsZDUgcikgewovLyAgICBzIDw8ICIoIiA8PCByLmEgPDwgIiwiIDw8IHIuYiA8PCAiKSI7CiAgICBzIDw8IHIuYjsKICAgIHJldHVybiBzOwogIH0KICBmcmllbmQgRmllbGQ1IG9wZXJhdG9yLShGaWVsZDUgY29uc3QgJngsIEZpZWxkNSBjb25zdCAmeSkgewogICAgRmllbGQ1IHI7CiAgICByLmEgPSB4LmEgLSB5LmE7IHIuYiA9IHguYiAtIHkuYjsKICAgIHJldHVybiByOwogIH0KICBmcmllbmQgRmllbGQ1IG9wZXJhdG9yKihGaWVsZDUgY29uc3QgJngsIEZpZWxkNSBjb25zdCAmeSkgewogICAgRmllbGQ1IHI7CiAgICByLmEgPSB4LmEgKiB5LmEgKyBSYXRpbyg1LCAxKSAqIHguYiAqIHkuYjsKICAgIHIuYiA9IHguYSAqIHkuYiArIHguYiAqIHkuYTsKICAgIHJldHVybiByOwogIH0gIAp9OwoKaW50NjRfdCBmaWIoaW50IG4pIHsKICBzdGF0aWMgaW50NjRfdCB0MSA9IDEsIHQyID0gMTsKICBpZiAobiA9PSAxIHx8IG4gPT0gMikKICAgIHJldHVybiAxOwogIGludDY0X3QgcyA9IHQxICsgdDI7CiAgdDEgPSB0MjsgdDIgPSBzOwogIHJldHVybiBzOwp9CgpGaWVsZDUgRmllbGQ1UG93ZXIoRmllbGQ1IGEsIGludCBuKSB7IC8qID1hXm4gKi8KICB1bnNpZ25lZCBpbnQgbWFzayA9IDEgPDwgKHNpemVvZihpbnQpICogOCAtIDEpOwogIEZpZWxkNSByKFJhdGlvKDEsIDEpLCBSYXRpbygwLCAxKSk7CiAgZm9yICg7OykgewogICAgaWYgKChuICYgbWFzaykgPiAwKQogICAgICByID0gciAqIGE7CiAgICBtYXNrID0gKG1hc2sgPj4gMSk7CiAgICAvKiBvdXQgb2YgbG9vcCAqLwogICAgaWYgKG1hc2sgPT0gMCkKICAgICAgYnJlYWs7CiAgICByID0gciAqIHI7CiAgfQogIHJldHVybiByOwp9CgppbnQgY29uc3QgTiA9IDkzOwppbnQgbWFpbigpIHsKICBGaWVsZDUgcGhpMShSYXRpbygxLCAyKSwgUmF0aW8oMSwgMikpOwogIEZpZWxkNSBwaGkyKFJhdGlvKDEsIDIpLCBSYXRpbygtMSwgMikpOwoKICBmb3IgKGludCBuID0gMTsgbiA8PSBOOyBuKyspIHsKICAgIGludDY0X3QgcyA9IGZpYihuKTsKCiAgICBGaWVsZDUgcjEsIHIyLCByMzsKICAgIHIxID0gRmllbGQ1UG93ZXIocGhpMSwgbik7CiAgICByMiA9IEZpZWxkNVBvd2VyKHBoaTIsIG4pOwogICAgcjMgPSByMSAtIHIyOwoKICAgIHN0ZDo6Y291dCA8PCBuIDw8ICI6OiAiIDw8IHMgPDwgIiA6ICIgPDwgcjMgPDwgc3RkOjplbmRsOwogIH0KICByZXR1cm4gMDsKfQovKiBlbmQgKi8KLy83NTQwMTEzODA0NzQ2MzQ2NDI5Ci8vOTIyMzM3MjAzNjg1NDc3NTgwNwoK