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
103
104
105
106
107
108
109
110
111
112
113
114
import java.math.*;
import java.util.*;

public class fib {

  static BigInteger[] dec = new BigInteger[50];

  static void calc_dec() {
    dec[0] = BigInteger.valueOf(1);
    for (int i = 1; i < 50; ++i)
      dec[i] = dec[i - 1].multiply(BigInteger.valueOf(10));
  }

  static BigInteger period(int d) {
    if (d == 1) return BigInteger.valueOf(60);
    if (d == 2) return BigInteger.valueOf(300);
    return dec[d - 1].multiply(BigInteger.valueOf(15));
  }

  static BigInteger[] mult(BigInteger[] a, BigInteger[] b, BigInteger mod) {
    BigInteger[] r = new BigInteger[4];
    r[0] = a[0].multiply(b[0]).mod(mod).add(a[1].multiply(b[2]).mod(mod)).mod(mod);
    r[1] = a[0].multiply(b[1]).mod(mod).add(a[1].multiply(b[3]).mod(mod)).mod(mod);
    r[2] = a[2].multiply(b[0]).mod(mod).add(a[3].multiply(b[2]).mod(mod)).mod(mod);
    r[3] = a[2].multiply(b[1]).mod(mod).add(a[3].multiply(b[3]).mod(mod)).mod(mod);
    return r;
  }

  static BigInteger calc_fib(BigInteger k, BigInteger mod) {
    BigInteger r[] = new BigInteger[4];
    r[0] = BigInteger.valueOf(1); 
    r[2] = BigInteger.valueOf(1);
    r[1] = BigInteger.valueOf(0);
    r[3] = BigInteger.valueOf(0);
    BigInteger x[] = new BigInteger[4];
    x[0] = BigInteger.valueOf(1); 
    x[2] = BigInteger.valueOf(1);
    x[1] = BigInteger.valueOf(1);
    x[3] = BigInteger.valueOf(0);
    while (k.compareTo(BigInteger.valueOf(0)) != 0) {
      if (k.mod(BigInteger.valueOf(2)).intValue() == 1)
        r = mult(r, x, mod);
      x = mult(x, x, mod);
      k = k.divide(BigInteger.valueOf(2));
    }
    return r[1];
  }

  static BigInteger debug;
  static BigInteger res;

  static final boolean do_debug = false;

  static boolean dfs(BigInteger target, BigInteger cur, int matched, int total, BigInteger pos) {
    if (matched == total) { res = pos; if (false) debug = calc_fib(pos, dec[50 - 1]); return true; }
    BigInteger prev = period(matched), next = period(matched + 1);
    BigInteger mod = dec[matched + 1];
    cur = target.mod(mod);
    for (BigInteger t = pos; t.compareTo(next) < 0; t = t.add(prev)) {
      BigInteger fib = calc_fib(t, mod);
      if (fib.compareTo(cur) == 0)
        if (dfs(target, cur, matched + 1, total, t)) return true;
    }
    return false;
  }

  static boolean try_solve(String s) {
    int total = s.length();
    BigInteger target = new BigInteger(s);
    for (int i = 0; i < 60; ++i) {
      BigInteger fib = calc_fib(BigInteger.valueOf(i), BigInteger.valueOf(10));
      if (fib.intValue() == target.mod(BigInteger.valueOf(10)).intValue())
        if (dfs(target, fib, 1, total, BigInteger.valueOf(i))) return true;
    }
    return false;
  }

  static final int tests = 1;

  static void success() {
    if (tests == 1) {
      if (do_debug) System.out.println(debug);
      System.out.println(res);
    }
    else
      System.out.println("TAK");
  }

  public static void main(String[] args) {
    calc_dec();
    Scanner scanner = new Scanner(System.in);
    for (int q = 0; q < tests; ++q) {
      String s = scanner.nextLine();
      if (s.charAt(0) == '0') {
        if (!try_solve(s))
          System.out.println("NIE");
        else {
          for (int i = 1; ; ++i) {
            if (try_solve(i + s)) {
              success();
              break;
            }
          }
        }
      }
      else {
        if (!try_solve(s))
          System.out.println("NIE");
        else
          success();
      }
    }
  }
}