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
#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// Szybkie sprawdzanie, czy maksymalny palindrom ma długość dokładnie k
bool check_k(const string& s, int k) {
    int n = s.length();
    int max_len = 0;
    for(int i = 0; i < n; i++) {
        // Sprawdzanie palindromów nieparzystej długości
        int l = i, r = i;
        while(l >= 0 && r < n && s[l] == s[r]) {
            max_len = max(max_len, r - l + 1);
            l--; r++;
        }
        // Sprawdzanie palindromów parzystej długości
        l = i, r = i + 1;
        while(l >= 0 && r < n && s[l] == s[r]) {
            max_len = max(max_len, r - l + 1);
            l--; r++;
        }
    }
    return max_len == k;
}

// Ostre odcinanie ścieżek w DFS - jeśli dodana litera stworzyła za duży palindrom, przerywamy
bool has_greater_than_k(const string& s, int k) {
    int n = s.length();
    for (int len = k + 1; len <= n; len++) {
        int l = n - len;
        int r = n - 1;
        bool is_pal = true;
        while (l < r) {
            if (s[l] != s[r]) { is_pal = false; break; }
            l++; r--;
        }
        if (is_pal) return true;
    }
    return false;
}

// Błyskawiczny DFS dla najmniejszych k (k <= 3)
string dfs(int n, int k, string current) {
    if (has_greater_than_k(current, k)) return "";
    if (current.length() == n) {
        if (check_k(current, k)) return current;
        return "";
    }
    string res = dfs(n, k, current + "P");
    if (res != "") return res;
    res = dfs(n, k, current + "A");
    return res;
}

void solve() {
    int n, k;
    cin >> n >> k;
    
    // Dla k <= 3 maksymalna długość to raptem kilka(naście) znaków. 
    // Od razu odrzucamy niemożliwe duże 'n', by nie tracić czasu.
    if (k <= 3) {
        if (n > 20) {
            cout << "NIE\n";
        } else {
            string ans = dfs(n, k, "");
            if (ans == "") cout << "NIE\n";
            else cout << ans << "\n";
        }
        return;
    }
    
    // Dla k = 4 używamy magicznego nieskończonego słowa PAAPPA
    if (k == 4) {
        string S = "PAAPPA";
        string res = "";
        for(int i = 0; i < n; i++) res += S[i % 6];
        cout << res << "\n";
        return;
    }
    
    // Konstrukcje dla dowolnego n i k >= 5
    if (n == k) {
        cout << "P" << string(k - 2, 'A') << "P\n";
        return;
    }
    if (n == k + 1) {
        cout << "AP" << string(k - 2, 'A') << "P\n";
        return;
    }
    
    // Dla większych n osadzamy bezpiecznie palindrom długości k na początku,
    // a resztę wypełniamy magicznym ciągiem APPPAAP unikającym palindromów >= 6
    string res = "AP" + string(k - 2, 'A') + "PP";
    string S = "APPPAAP";
    int S_idx = 0;
    while (res.length() < n) {
        res += S[S_idx % S.length()];
        S_idx++;
    }
    cout << res << "\n";
}

int main() {
    // Standardowa ekstremalna optymalizacja I/O dla PA
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}