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
#include<bits/stdc++.h>
using namespace std;
const int N=9;
inline bool ispal(string s){
  auto t=s;
  return reverse(t.begin(),t.end()),s==t;
}
inline int lp(string s){
  int n=s.length();
  for(int l=n;l>1;l--)
    for(int i=0;i+l<=n;i++)
      if(ispal(s.substr(i,l)))return l;
  return 1;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  vector a(10,vector<string>(10));
  for(int l=1;l<10;l++)
    for(int S=0;S<1<<l;S++){
      string s;
      for(int i=0;i<l;i++)
        s+=S>>i&1?'P':'A';
      a[l][lp(s)]=s;
    }
  int t; cin>>t;
  while(t--){
    int n,k; cin>>n>>k;
    if(n<=9){
      if(a[n][k].empty())cout<<"NIE\n";
      else cout<<a[n][k]<<'\n';
    }
    else if(k<=3)cout<<"NIE\n";
    else{
      string s(k,'A');
      while(s.length()<=n)s+="PAPPAA";
      cout<<s.substr(0,n)<<'\n';
    }
  }
  return 0;
}