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
//Solution by Mikołaj Kołek

#include "bits/stdc++.h"
#define intin *istream_iterator<int>(cin)

using namespace std;

vector<int> manacher(const string &in) {
	string w = "#";
	for(const auto &ch : in)
		w.append(string(1, ch) + "#");

	vector<int> res(w.size() + 1);
	res[0] = 1;
	for(int i = 1, j = 1, k; i < w.size(); i += k, j -= k) {
		while(i - j >= 0 and i + j < w.size() and w[i - j] == w[i + j])
			j++;

		res[i] = j;
		for(k = 1; k + res[i - k] < j; k++)
			res[i + k] = res[i - k];
	}

	return res;
}

void brute(int n, int k) {
	for(int i = 0; i < (1 << n); i++) {
		string str;
		for(int j = n - 1; j >= 0; j--)
			str.push_back((i & (1 << j)) ? 'P' : 'A');
		
		auto manacherRes = manacher(str);
		int res = *max_element(manacherRes.begin(), manacherRes.end()) - 1;
		
		if(res == k) {
			cout << str << "\n";
			return;
		}
	}
	
	cout << "NIE\n";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int t = intin;
	while(t--) {
		int n = intin, k = intin;
		if(n <= 10) {
			brute(n, k);
			continue;
		}
		
		if(k < 4) {
			cout << "NIE\n";
			continue;
		}
		
		for(int i = 0; i < k; i++)
			cout << "A";
		for(int i = k, state = 0; i < n; i++, state = (state + 1) % 6) {
			if(state == 0 or state == 2 or state == 3)
				cout << "P";
			else
				cout << "A";
		}
		cout << "\n";
	}
	
	return 0;
}

/*
5
11 1
11 3
11 4
11 6
11 8
*/