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
#include<cstdio>
#include<bits/stdc++.h>
#define LL long long int 

using namespace std;
// Funkcja przeprowadza test Millera-Rabina dla liczby x przy podstawie n 
bool MaR(LL x, LL n) { 
	if (x >= n) return 0; 
	LL d = 1, y; 
	int t = 0, l = n - 1; 
	while (!(l & 1)) { 
		++t; 
		l >>= 1; 
	} 
	for (; l > 0 || t--; l >>= 1) 
	{ 
		if (l & 1) d = (d * x) % n; 
		if (!l) { 
		x = d; 
		l = -1; 
		} 
		y = (x * x) % n; // Jeśli test Millera wykrył, że liczba nie jest pierwsza, to zwróć prawdę 
		if (y == 1 && x != 1 && x != n - 1) return 1; 
		x = y; 
	} // Jeśli nie jest spełnione założenie twierdzenia Fermata, to liczba jest // złożona 
	return x != 1; 
 } // Funkcja sprawdza, czy dana liczba x jest pierwsza. W tym celu wykonuje test // Millera-Rabina przy podstawie 2, 3, 5, 7 
 bool isPrime(int x) { 
	return !(x < 2 || MaR(2, x) || MaR(3, x) || MaR(5, x) || MaR(7, x)); 
 }
 
long long int tab[20][20];
std::vector<int> getVector(LL n)
{
	vector<int> res;
	while(n)
	{
		res.push_back(n%10);
		n/=10;
		
	}
	reverse(res.begin(),res.end());
	return res;
}
bool checkIfPrime(vector<int> num,int b, int e)
{
	LL n=0;
	for(int i=b;i<e;++i)
	{
		n=n*10+num[i];
	}
	return isPrime(n);
}
bool solve(vector<int> num,int b,int e)
{
	if(num[b] == 0) return false;
	if(tab[b][e])return tab[b][e] == 1;
	if(!(b == 0 && e == num.size()) && checkIfPrime(num,b,e))
	{
		tab[b][e] = 1;
		return true;
	}
	for(int i=b+1;i<e;++i)
	{
		if(solve(num,b,i) && solve(num,i,e))
		{
			tab[b][e] = 1;
			return true;
		}
	}
	tab[b][e] = 2;
	return false;
}

int main()
{
	LL a;
	cin >> a;
	auto num = getVector(a);
	if(solve(num,0,num.size()))cout << "TAK";else cout << "NIE";
	
	return 0;
}