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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define st first
#define nd second
#define pii pair<ll,ll>
#define pb push_back
#define pf push_front
#define lll __int128
#define si size()
#define int ll
const int A=1e6+3;
map<int,string>m[25];
int il(int ma,int n){
    vector<int>v(n);
    for(int i=0;i<n;i++)
        v[i]=(ma>>i)&1;
    int maxi=0;
    for(int i=0;i<n;i++){
        int l=i,r=i;
        while(l>0&&r<n-1&&v[l-1]==v[r+1]){
            l--;
            r++;
        }
        maxi=max(maxi,r-l+1);
    }
    for(int i=0;i<n-1;i++){
        if(v[i]!=v[i+1]) continue;
        int l=i,r=i+1;
        while(l>0&&r<n-1&&v[l-1]==v[r+1]){
            l--;
            r++;
        }
        maxi=max(maxi,r-l+1);
    }
    return maxi;
}
string sr(int ma,int n){
    string s;
    for(int i=0;i<n;i++){
        if((ma>>i)&1) s+="A";
        else s+="P";
    }
    return s;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    
    for (int n=1;n<=10;n++){
        
        for(int i=0;i<(1<<n);i++){
            int a=il(i,n);
            m[n][a]=sr(i,n);
        }
    //  //   cout<<n<<": \n";
    //     for(int i=1;i<=n;i++) {
    //    //     cout<<"    "<<i<<": ";
    //         if(!m[i].si) cout<<"-\n";
    //         else cout<<m[i]<<'\n';
    //     }
    //     cout<<'\n';
    }
    while(t--){
        int n,k;
        cin>>n>>k;
        if(n<=9){
            if(m[n][k].si) cout<<m[n][k]<<'\n';
            else cout<<"NIE\n";
            continue;
        }
        if(k<=3){
            cout<<"NIE\n";
            continue;
        }
        string s;
        for(int i=0;s.si<n;i++){
            if(i%4==0) s+="A";
            if(i%4==1) s+="P";
            if(i%4==2) s+="AA";
            if(i%4==3) s+="PP";
        }
        while(s.si>n-k) s.pop_back();
        reverse(s.begin(),s.end());
        if(s.back()=='A'){
            while(s.si<n) 
                s+="P";
        }
        else{
            while(s.si<n) 
                s+="A";
        }
        cout<<s<<'\n';
    }
    return 0; 
}