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
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <string_view>
#include <vector>

using namespace std;
using ll = long long;
#define all(a) begin(a), end(a)

bool is_pali(string_view s) {
    int n = s.size();
    for (int i = 0; n - 1 - i > i; i++) {
        if (s[i] != s[n - 1 - i]) {
            return false;
        }
    }
    return true;
}

bool check(string_view s, int k) {
    for (int i = 0; i + k <= s.size(); i++) {
        if (is_pali(s.substr(i, k))) {
            return true;
        }
    }
    return false;
}

string generate(string s, int k, int n) {
    if (check(s, k + 1) || check(s, k + 2)) {
        return "";
    }
    // cerr << s << "\n";
    if (s.size() == n && check(s, k)) {
        return s;
    }

    if (s.size() >= n) {
        return "";
    }

    if (auto t = generate(s + 'A', k, n); t.size()) {
        return t;
    }
    if (auto t = generate(s + 'P', k, n); t.size()) {
        return t;
    }
    return "";
}

bool works(string_view s, int k) { return check(s, k) && !check(s, k + 1) && !check(s, k + 2); }

vector<vector<string>> small(5, vector<string>(20));
void init() {
    for (int k = 1; k < 4; k++) {
        for (int n = 1; n < 20; n++) {
            small[k][n] = generate("", k, n);
        }
    }
}

string solve(int n, int k) {
    if (k < 4) {
        if (n >= small[k].size()) {
            return "";
        }
        return small[k][n];
    }

    string s;
    while (s.size() < n) {
        s += "APPAAP";
    }
    s.resize(n);
    if (k == 4) {
        return s;
    }
    s.resize(n - k);
    char b = s.empty() ? 'A' : 'A' ^ 'P' ^ s.back();
    auto t = s + string(k, b);
    if (k > 6) {
        return t;
    }
    auto x = generate(s, k, n);
    // cerr << n << " " << k << "\n";
    assert(works(x, k));
    return x;
}

int rand(int l, int r) { return l + rand() % (r - l + 1); }

void solve() {
    int n = rand(1, 1000), k = rand(1, n);
    cin >> n >> k;
    auto s = solve(n, k);
    if (s.empty()) {
        cout << "NIE\n";
        return;
    }

    // cerr << n << " " << k << " -> " << s << "\n";
    assert(s.size() == n);
    assert(works(s, k));
    cout << s << "\n";
}

int main() {
    init();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // while (1) {
    //     solve();
    // }

    int q = 1;
    cin >> q;
    while (q--) {
        solve();
    }
}