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
#include <bits/stdc++.h>
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define V vector
using namespace std;
typedef long long ll;
int mod = 119<<23|1;
ll infll = 2e18;

template<typename... Args>
void read(Args&... args) {
    auto read_one = [&](auto &a) {
        a = 0; int c = getchar_unlocked();
        while (c < '0' || '9' < c) c = getchar_unlocked();
        while ('0' <= c && c <= '9') a = a*10+c-'0', c = getchar_unlocked();
    };
    return (read_one(args), ...);
}

void answer() {
    int n, k; scanf("%d%d", &n, &k);
    if (n <= 8) {
        V<int> s(n), res;
        for (int m = 0; m < 1<<n; ++m) {
            int max_len = 0;
            for (int i = 0; i < n; ++i) s[i] = m & (1<<i) ? 1 : 0;
            for (int i = 0; i < n; ++i) {
                int len = -1;
                for (int j = 0; i-j >= 0 && i+j < n; ++j)
                    if (s[i-j] != s[i+j]) break;
                    else (++len)++;
                max_len = max(max_len, len);
                
                len = 0;
                for (int j = 0; i-j >= 0 && i+j+1 < n; ++j)
                    if (s[i-j] != s[i+j+1]) break;
                    else (++len)++;
                max_len = max(max_len, len);
            }
            if (max_len == k){ res = s; break; }
        }
        if (ssize(res)) {
            for (int u : res) printf(u ? "P" : "A");
            printf("\n");
        }
        else printf("NIE\n");
        return;
    }
    if (k < 4) return void(printf("NIE\n"));
    string res;
    V<string> p2 = {"PPAA", "PAPP", "AAPA"}, p(3);

    int N = n-k;
    for (int i = 0; i < 3; ++i) p[i] = p2[(i-(N/4)%3+3)%3];

    // for (int i = 0; i < 3; ++i) cout << p[i] << " ";
    // cout << "\n";

    for (int i = 4-(N%4); i < 4; ++i) res += p[2][i];
    int id = 0;
    while (ssize(res) + 4 <= N)
        res += p[id++], id %= 3;
    
    if (!ssize(res) || res.back() == 'A')
        for (int i = 0; i < k; ++i) res += 'P';
    else
        for (int i = 0; i < k; ++i) res += 'A';

    cout << res << "\n";
}
int main() {
    int T = 1; scanf("%d", &T);
    for (++T; --T; ) answer();
    return 0;
}