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
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
string getsmartpalindrom(int n, int k) {
    string res(k,'P');
    while (res.size()<n)
        res.append("AAPAPP");
    return res.substr(0,n);
}
size_t maxpalindrom(string s) {
    for (int l=s.size();l>1;--l) {
        for (int i=0;i+l<=s.size();++i) {
            for (int k=0;k+k<l;++k)
                if (s[i+k]!=s[i+l-k-1])goto no;
            return l;
        no:
            void();
        }
    }
    return 1;
}
vector<string> _getpalindrom(int n, int k) {
    if (k>3) return {getsmartpalindrom(n,k)};
    if (n>8) return {};
    if (k<1) return {};
    if (n==1&&k==1) return {"P","A"};
    if (n==1) return {};
    vector<string> h1 = _getpalindrom(n-1, k), h2 = _getpalindrom(n-1, k-1);
    vector<string> res;
    for (auto&& si : h1) {
        if (maxpalindrom(si+'A')==k)res.push_back(si+'A');
        if (maxpalindrom(si+'P')==k)res.push_back(si+'P');
    }
    for (auto&& si : h2) {
        if (maxpalindrom(si+'A')==k)res.push_back(si+'A');
        if (maxpalindrom(si+'P')==k)res.push_back(si+'P');
    }
    return res;
}
string getpalindrom(int n, int k) {
    auto res = _getpalindrom(n, k);
    if (res.empty()) return "NIE";
    return res.front();
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;cin>>t;
    while (t--) {
        int n,k;cin>>n>>k;
        cout << getpalindrom(n, k) << '\n';
    }
}