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
#pragma GCC optimize("O3,unroll-loops,inline")
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

array<vi, 2> manacher(const string& s) {
	int n = sz(s);
	array<vi,2> p = {vi(n+1), vi(n)};
	rep(z,0,2) for (int i=0,l=0,r=0; i < n; i++) {
		int t = r-i+!z;
		if (i<r) p[z][i] = min(t, p[z][l+t]);
		int L = i-p[z][i], R = i+p[z][i]-!z;
		while (L>=1 && R+1<n && s[L-1] == s[R+1])
			p[z][i]++, L--, R++;
		if (R>r) l=L, r=R;
	}
	return p;
}

map<pair<int,int>,string> cc;

mt19937 rng(42343423);
int rnd(int l, int r){
    return uniform_int_distribution(l,r)(rng);
}

void solve(){
    int n,k; cin >> n >> k;
    if (n < 16){
        if (cc.count({n,k})){
            cout << cc[{n,k}] << '\n';
        }else{
            cout << "NIE\n";
        }
    }else{
        if (k < 4) {
            cout << "NIE\n";
        }else{
            string sol(k,'A');
            string papaap = "PPAPAA";
            rep(i,0,n-k) sol.push_back(papaap[i%6]);
            cout << sol << '\n';
            // auto rec = [&](auto&& rec) -> bool {
            //     if (sol.size() == n){
            //         cout << sol << '\n';
            //         return 1;
            //     }

            //     int xx = rnd(0,1);
            //     rep(i,0,2){
            //         sol.push_back(xx ? 'A' : 'P');
            //         int gd = 2;
            //         if (k < 24){
            //             gd = 0;
            //             if (sz(sol) >= k+2) rep(i,0,(k+2)/2) {
            //                 if (sol[sz(sol)-1-i] != sol[sz(sol)-k-2+i]){
            //                     gd++;
            //                     break;
            //                 }
            //             }else gd++;
            //             rep(i,0,(k+1)/2) {
            //                 if (sol[sz(sol)-1-i] != sol[sz(sol)-k-1+i]){
            //                     gd++;
            //                     break;
            //                 }
            //             }
            //         }
            //         if (gd==2){
            //             if (rec(rec)) return 1;
            //         }
            //         sol.pop_back();
            //         xx ^= 1;
            //     }

            //     return 0;
            // };
            // rec(rec);
        }
    }
}

/*

APAAPAPPAPA
*/

int main(){
    cin.tie(NULL),ios::sync_with_stdio(false);

    rep(n,1,16){
        // cout << "n: " << n << '\n';

        rep(msk,0,1<<n){
            string s(n,'A');
            rep(j,0,n) if (msk&(1<<j)) s[j] = 'P';
            auto [o,e] = manacher(s);
            cc[{n,max(*max_element(all(o))*2, *max_element(all(e))*2+1)}] = s;
        }

        // for(auto [k,v] : cc) cout << k << ' ' << v << '\n';
    }
    
    int t; cin >> t;
    while(t--) solve();
}

/*

k 1 (k-1)/2 k-1-(k-1)/2

*/