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

using namespace std;

inline uint32_t findMaxPowerOfTwo(uint64_t n) {
    assert(n % 2 == 0);
    uint32_t result = 0;
    while (((n >> result) & 1) == 0)
        ++result;
    return result;
}

uint64_t fastPow(const uint64_t value, const uint32_t power) {
    if (power == 1)
        return value;
    else if ((power % 2) == 1)
        return value * fastPow(value, power - 1);
    else {
        const uint64_t subResult = fastPow(value, power / 2);
        return subResult * subResult; 
    }
}

uint64_t fastPowModulo(const uint64_t value, const uint32_t power, const uint64_t modulo) {
    if (power == 0)
        return 1;
    else if (power == 1)
        return value % modulo;
    else if ((power % 2) == 1)
        return (value * fastPow(value, power - 1)) % modulo;
    else {
        const uint64_t subResult = fastPow(value, power / 2);
        return (subResult * subResult) % modulo; 
    }
}

bool isAnyModAligned(const uint64_t n, const uint32_t a, const uint32_t s, const uint64_t rest) {
    for (uint32_t i = 0; i < s; ++i) {
        if (fastPowModulo(a, (1 << i) * rest, n) == n - 1)
            return false;
    }
    return true;
}

inline bool isPrime(const uint64_t n) {
    const uint32_t precision = 7;

    if (n % 2 == 0)
        return n == 2;

    const uint32_t maxPowerOfTwo = findMaxPowerOfTwo(n - 1);
    const uint64_t rest = n / (1 << static_cast<uint64_t>(maxPowerOfTwo));

    const uint32_t aValues[] = {2, 3, 5, 7, 11, 13, 17};
    for (uint32_t i = 0; i < precision; ++i) {
        assert(i < sizeof(aValues) / sizeof(aValues[0]));

        const uint32_t a = aValues[i];
        if (fastPow(a, rest) % n != 1 && isAnyModAligned(n, a, maxPowerOfTwo, rest))
            return false;
    }

    return true;
}


int main(int, char *[]) {
    ios_base::sync_with_stdio(false);

    uint64_t in;
    cin >> in;

    uint64_t a = in / 10, b = in % 10;
    uint64_t power = 10;
    while (a != 0) {
        if (a * power + b == in) {
            if (isPrime(a) && isPrime(b)) {
                cout << "TAK" << endl;
                return 0;
            }
        }

        b += (a % 10) * power;
        a /= 10;
        power *= 10;
    }

    cout << "NIE" << endl;
}