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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define st first
#define nd second

string preprocessed[11][11];
void solve() {
    int n, k;
    cin >> n >> k;
    if (n <= 10) {
        if (preprocessed[n][k].empty()) cout << "NIE\n";
        else cout << preprocessed[n][k] << "\n";
        return;
    }
    if (k < 4) {
        cout << "NIE\n";
        return;
    }
    for (int i = 0; i < k; i++) cout << 'P';
    string pattern = "APAAPP";
    for (int i = 0; i < n-k; i++) cout << pattern[i%6];
    cout << '\n';

}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    for (int n = 1; n <= 10; n++) {
        for (int b = 0; b < (1<<n); b++) {
            int max_r = 1;
            for (int i = 0; i < n; i++){
                int r = 0;
                while ((i-(r+1) >= 0 )&& (i+(r+1) < n) && (((b>>(i-(r+1)))&1) == ((b>>(i+r+1))&1))) r++;
                max_r = max(max_r, 2*r+1);
    
            }
            for (int i = 0; i < n-1; i++) {
                int r = 0;
                while ((i-(r) >= 0 )&& (i+(r+1) < n) && (((b>>(i-(r)))&1) == ((b>>(i+r+1))&1))) r++;
                max_r = max(max_r, 2*r);
            }
            // if (max_r <= 5) {
            //     cout << max_r << ": ";
            //     cout << '\n';
            // }
            if (preprocessed[n][max_r].size() == 0) {
                string s;
                for (int i = 0; i<n; i++) {
                    if (b&(1<<i)) s.push_back('P');
                    else s.push_back('A');
                }
                preprocessed[n][max_r] = s;
            }
        }
    }
    // cout << preprocessed[20][3] << '\n';
    // for (int i = 1; i <= 20; i++) cout << preprocessed[i][3] << '\n';
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}