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
#include <iostream>
#include <algorithm>

using namespace std;

#define MAX_PRIMES 227646
long long primes[MAX_PRIMES];
#define MAX_CHECK 3162277
bool checkPrime[MAX_CHECK];
int numberOfPrimes = 8;

long long tenToThePowerOf(int exp) {
    switch (exp) {
        case 0:
            return 1;
        case 1:
            return 10;
        case 2:
            return 100;
        case 3:
            return 1000;
        case 4:
            return 10000;
        case 5:
            return 100000;
        case 6:
            return 1000000;
        case 7:
            return 10000000;
        case 8:
            return 100000000;
        case 9:
            return 1000000000;
        case 10:
            return 10000000000;
        case 11:
            return 100000000000;
        case 12:
            return 1000000000000;
    }
}

void generatePrimes() {
    for (int i = 2; i < MAX_CHECK; ++i) {
        checkPrime[i] = true;
    }
    for (int candidate = 2; candidate < MAX_CHECK; ++candidate) {
        if(!checkPrime[candidate])
            continue;
        for (int multiple = 2*candidate; multiple < MAX_CHECK; multiple += candidate) {
            checkPrime[multiple] = false;
        }
    }
    numberOfPrimes = 0;
    for (int j = 0; j < MAX_CHECK; ++j) {
        if(checkPrime[j]) {
            primes[numberOfPrimes] = j;
            numberOfPrimes++;
        }
    }
}

std::pair<long long, long long> splitNumber(long long number, int place) {
    std::pair<long long, long long> pair;
    //place >= 1 && place < 13
    pair.first = number % tenToThePowerOf(place);
    pair.second = number / tenToThePowerOf(place);
    return pair;
}

bool isPrime(long long n, long long primePool[], int poolSize) {
    if(binary_search(primePool, primePool+poolSize, n))
        return true;

    for(auto i = 0; i < poolSize; i++) {
        if(n % primePool[i] == 0)
            return false;
    }
    return true;
}

bool isGood(long long number) {
    for (int place = 1; place < 13; ++place) {
        auto split = splitNumber(number, place);
        if(split.first == 0 || split.second == 0)
            continue;
        if(split.second < tenToThePowerOf(place-1))
            continue;
        if(
                isPrime(split.first, primes, numberOfPrimes) &&
                isPrime(split.second, primes, numberOfPrimes)
            ) {
            return true;
        }
    }
    return false;
}

int main(int argc, char **argv) {
    std::ios_base::sync_with_stdio(false);

    long long n;
    cin >> n;
    generatePrimes();
    if(isGood(n)) {
        cout << "TAK";
    } else {
        cout << "NIE";
    }

    return 0;
}