1. include <bits/stdc++.h>
2.  
3. using namespace std;
4.  
5. class PalindromicSubstring {
6. private:
7.     int length;
8.     string text;
9.     int *r;
10.  
11. public:
12.     PalindromicSubstring(const string &text) {
13.         this->text = " ";
14.         for (int i = 0; i < text.length(); i++) {
15.             this->text += text[i];
16.             this->text += '#';
17.         }
18.         this->length = (int) (2 * text.length() - 1);
19.         this->r = new int[this->length + 1];
20.     }
21.  
22.     virtual ~PalindromicSubstring() {
23.         delete[] r;
24.     }
25.  
26.     void computeRadius();
27.  
28.     void printRadius();
29.  
30.     bool isPalindrome(int p, int q);
31. };
32.  
33. void PalindromicSubstring::computeRadius() {
34.     int farPos = 1, cur = 2;
35.     r[1] = 0;
36.     while (cur <= length) {
37.         if (farPos + r[farPos] < cur) {
38.             r[cur] = 0;
39.             while (cur + r[cur] <= length && cur - r[cur] >= 1 && text[cur + r[cur]] == text[cur - r[cur]]) r[cur]++;
40.             r[cur]--;
41.             farPos = cur;
42.         } else {
43.             int opp = 2 * farPos - cur;
44.             if (cur + r[opp] < farPos + r[farPos]) {
45.                 r[cur] = r[opp];
46.             } else {
47.                 r[cur] = farPos + r[farPos] - cur;
48.                 while (cur + r[cur] <= length && cur - r[cur] >= 1 && text[cur + r[cur]] == text[cur - r[cur]])
49.                     r[cur]++;
50.                 r[cur]--;
51.                 farPos = cur;
52.             }
53.         }
54.         cur++;
55.     }
56. }
57.  
58. void PalindromicSubstring::printRadius() {
59.     for (int i = 1; i <= PalindromicSubstring::length; i++) {
60.         cout << text[i];
61.     }
62.     cout << endl;
63.     for (int i = 1; i <= PalindromicSubstring::length; i++) {
64.         cout << r[i];
65.     }
66.     cout << endl;
67. }
68.  
69. bool PalindromicSubstring::isPalindrome(int p, int q) {
70.     p = 2 * p - 1;
71.     q = 2 * q - 1;
72.     if (r[(p + q) / 2] >= (q - p) / 2) {
73.         return true;
74.     } else {
75.         return false;
76.     }
77. }
78.  
79. int main() {
80.     ios_base::sync_with_stdio(false);
81.  
82.     int z;
83.     cin >> z;
84.  
85.     while (z--) {
86.         string w;
87.         cin >> w;
88.  
89.         PalindromicSubstring palindromicSubstring(w);
90.         palindromicSubstring.computeRadius();
91.  
92.         int q;
93.         cin >> q;
94.  
95.         while (q--) {
96.             int a, b;
97.             cin >> a >> b;
98.             cout << (palindromicSubstring.isPalindrome(a, b) ? "TAK" : "NIE") << endl;
99.         }
100.     }
101.  
102.     return 0;
103. }