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
#include <bits/stdc++.h>
using namespace std;


template <typename V> std::vector<int> manacher(const V& S) {
	int N = int(S.size());
	std::vector<int> res(2*N+1, 0);
	for (int i = 1, j = -1, r = 0; i < 2*N; i++, j--) {
		if (i > r) {
			r = i+1, res[i] = 1;
		} else {
			res[i] = res[j];
		}
		if (i+res[i] >= r) {
			int b = r>>1, a = i-b;
			while (a > 0 && b < N && S[a-1] == S[b]) {
				a--, b++;
			}
			res[i] = b-a, j = i, r = b<<1;
		}
	}
	return res;
}

int longest_pal(string S){
	auto res = manacher(S);
	return *max_element(res.begin(), res.end());
}

string solve(int N, int K){
	// for(int c = 0; c < (1 << N); c++){
	// 	string r;
	// 	for(int i = 0; i < N; i++) r += "AP"[(c >> i) & 1];
	// 	if(longest_pal(r) == K) return r;
	// }
	// return "";
	if(2*K >= N) return string(K, 'A') + string(N-K, 'P');
	if(K == 1) return "";
	if(K == 2) return "";
	if(K == 3){
		if(N == 7) return "AAAPAPP";
		if(N == 8) return "AAAPAPPP";
		return "";
	}
	string S = string(K, 'A');
	while(S.size() < N) S += "PPAPAA";
	S.resize(N);
	return S;
}

void solve_case(){
	int N, K;
	cin >> N >> K;
	string res = solve(N, K);
	cout << (!res.empty() ? res : "NIE") << '\n';
}

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	// for(int N = 1; N <= 20; N++){
	// 	for(int K = 1; K <= N; K++){
	// 		string res = solve(N, K);
	// 		if(!res.empty()) assert(longest_pal(res) == K);
	// 	}
	// }
	int T;
	cin >> T;
	while(T--) solve_case();
}