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
/* Autor: Adam Bac
 * Zadanie: DRU
 * Potyczki Algorytmiczne 2017
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll str_to_int(const string & str) {
    ll ret = 0;
    for(char c: str) {
        ret *= 10;
        ret += c - '0';
    }
    return ret;
}

ll pow_mod(ll a, ll n, ll m) {
    if(n == 0) return 1;
    ll x = pow_mod(a, n / 2, m);
    x = (x * x) % m;
    if(n % 2 == 0) return x;
    else return (x * a) % m;
}

bool test_prime(ll p) {
    ll pm = p - 1;
    ll s = __builtin_ctz(pm);
    ll max_pow_of_2 = pm & (-pm);
    ll d = pm / max_pow_of_2;
    
    vector<ll> primes = {2, 3, 5, 7, 11, 13, 17, 23, 29, 31, 37};
    for(ll prime: primes) {
        if(prime == p) return true;
        ll x = pow_mod(prime, d, p);
        if(x == 1 || x == p - 1) continue;
        bool cont = true;
        for(int i = 1; i < s && cont; i++) {
            x = (x * x) % p;
            if(x == 1) return false;
            if(x == p - 1) cont = false;
        }
        if(cont) return false;
    }

    return true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string str;
    cin >> str;

    for(int div = 1; div < (int) str.size(); div++) {
        if(str[div] == '0') continue;
        if(test_prime(str_to_int(str.substr(0, div))) &&
           test_prime(str_to_int(str.substr(div)))) {
            cout << "TAK\n";
            return 0;
        }
    }

    cout << "NIE\n";
}