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
#include <bits/stdc++.h>

using namespace std;
const int MX = 12, INF = 1e6;
int s[MX][MX];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    for(auto i = 0; i < MX; ++i){
        for(auto j = 0; j < MX; ++j){
            s[i][j] = INF;
        }
    }
    s[1][1] = 0;
    for(auto n = 2; n <= 10; ++n){
        for(auto mask = 0; mask < (1<<n); ++mask){
            int maxi = 0;
            for(auto c = 0; c < n; ++c){
                for(auto i = 0; i < n; ++i){
                    int l = c-i, r = c+i;
                    if(l < 0 || r >= n || bool(mask&(1<<l)) != bool(mask&(1<<r))) break;
                    maxi = max(maxi, r-l+1);
                }
            
            }
            for(auto c1 = 0; c1 < n-1; ++c1){
                int c2 = c1+1;
                for(auto i = 0; i < n; ++i){
                    int l = c1-i, r = c2+i;
                    if(l < 0 || r >= n || bool(mask&(1<<l)) != bool(mask&(1<<r))) break;
                    maxi = max(maxi, r-l+1);
                }
            }
            s[n][maxi] = mask;
        }
    }
    string pat = "APAAPP";
    int q; cin >> q;
    while(q--){
        int n, k; cin >> n >> k;
        if(n <= 10){
            if(s[n][k] == INF) cout << "NIE\n";
            else{
                int x = s[n][k];
                for(auto i = 0; i < n; ++i){
                    cout << (x%2 ? "A" : "P");
                    x /= 2;
                }
                cout << endl;
            }
            continue;
        }
        if(k < 4){
            cout << "NIE\n";
            continue;
        }
        for(auto i = 0; i < k; ++i) cout << "P";
        for(auto i = 0; i < n-k; ++i) cout << pat[i%6];
        cout << endl;
    }
}