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
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cstdint>

using lli = long long int;

static const lli SIEVE_SIZE = 1000 * 1000;

bool sieve[SIEVE_SIZE] = { false };

void initSieve() {
  sieve[0] = true;
  sieve[1] = true;
  for (int i = 4; i < SIEVE_SIZE; i += 2) {
    sieve[i] = true;
  }
  for (int p = 3; p * p < SIEVE_SIZE; p += 2) {
    if (sieve[p]) {
      continue;
    }
    for (int i = p * p; i < SIEVE_SIZE; i += p) {
      sieve[i] = true;
    }
  }
}

bool isPrime(lli n) {
  if (n <= 1) {
    return false;
  }
  if (n < SIEVE_SIZE) {
    // fprintf(stderr, "%lld: %c\n", n, sieve[n] ? 'f' : 't');
    return !sieve[n];
  }
  if (n % 2 == 0) {
    return false;
  }
  for (lli p = 3; p * p <= n; p += 2) {
    if (!sieve[p] && (n % p == 0)) {
      return false;
    }
  }
  return true;
}

int main() {
  initSieve();

  lli n;
  scanf("%lld", &n);

  lli left = n, right = 0;
  lli position = 1;

  while (left >= 10) {
    // Shift a digit from one side to another
    lli digit = left % 10;
    left /= 10;
    right += position * digit;
    position *= 10;
    // fprintf(stderr, "(%lld, %lld)\n", left, right);
    if (digit == 0) {
      continue;
    }

    const bool found = (left <= right)
      ? (isPrime(left) && isPrime(right))
      : (isPrime(right) && isPrime(left));
    if (found) {
      puts("TAK");
      return 0;
    }
  }

  puts("NIE");
  return 0;
}