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
#include <cstdio>
#include <vector>

using namespace std;

int a[6] = {1, 0, 1, 1, 0, 0};
vector<int> t;

int pal() {
  int best = 0;
  int n = t.size();

  for (int i=0; i<n; ++i) {
    int cnt = 0;
    for (int j=0; i-j>=0 && i+j<n; ++j) {
      if (t[i-j] == t[i+j]) ++cnt;
      else break;
    }
    best = max(best, cnt*2-1);
  }

  for (int i=0; i<n; ++i) {
    int cnt = 0;
    for (int j=0; i-j>=0 && i+j+1<n; ++j) {
      if (t[i-j] == t[i+j+1]) ++cnt;
      else break;
    }
    best = max(best, cnt*2);
  }
  return best;
}

bool res(int l, int k) {
  if (l > 0) {
    t.push_back(0);
    if (res(l-1, k)) return true;
    t.back() = 1;
    if (res(l-1, k)) return true;
    t.pop_back();
    return false;
  } else {
    return pal() == k;
  }
}

int main() {
  int tt; scanf("%d", &tt);

  while (tt--) {
    int n, k; scanf("%d %d", &n, &k);
    t.clear();
    if (n >= 9) {
      if (k < 4) {
        printf("NIE\n");
      } else {
        for (int i=0; i<k; ++i) printf("A");
        for (int i=0; i<n-k; ++i) printf("%c", a[i%6] ? 'P' : 'A');
        printf("\n");
      }
    } else {
      if (res(n, k)) {
        for (int i=0; i<n; ++i) printf("%c", t[i] ? 'P' : 'A');
        printf("\n");
      } else {
        printf("NIE\n");
      }
    }
  }

  return 0;
}