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
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef vector<vi> vvi;
typedef vector<bool> vb;

#define eb(x) emplace_back(x)
#define loop(i,a,b) for (int (i) = (a); (i) < b; (i)++)
#define rloop(i,a,b) for (int (i) = (a); (i) >= b; (i)--)

const int MOD = 1e9 + 7;
ll hash1[1000 * 1000 + 3];
ll hash2[1000 * 1000 + 3];
ll pot[1000 * 1000 + 3];
int res[1000 * 1000 + 3];

int podst,n,k;

bool czyPal(int l, int r)
{
	if (l < 1) return false;
	int dl = (r - l + 1);
	ll h1 = (hash1[r] - hash1[l-1] + MOD) % MOD;
	ll h2 = (((hash2[r] - (hash2[l - 1] * pot[dl]) % MOD + MOD) % MOD) * pot[l]) % MOD;
	return h1 == h2;
}

bool dfs(int it)
{
	if (it > n)
		return true;

	loop(i, 3, 5)
	{
		res[it] = i;
		hash1[it] = (hash1[it - 1] + res[it] * pot[it]) % MOD;
		hash2[it] = (hash2[it - 1] * podst + res[it]) % MOD;

		if (!czyPal(it - k, it) && !czyPal(it - k - 1, it))
			if (dfs(it + 1))
				return true;
	}
	return false;
}

void solve()
{
	cin >> n >> k;
	if (k > n)
	{
		cout << "NIE\n";
		return;
	} 


	loop(i, 1, k+1)
	{
		res[i] = 3;
		hash1[i] = (hash1[i - 1] + res[i] * pot[i]) % MOD;
		hash2[i] = (hash2[i - 1] * podst + res[i]) % MOD;
	}

	if (dfs(k + 1))
	{
		loop(i, 1, n + 1) { if (res[i] == 3) cout << 'P'; else cout << 'A'; }
		cout << '\n';
	}
	else
		cout << "NIE\n";
}
int main()
{
	srand(time(0));
	pot[0] = 1;
	podst = (rand() % 200) + 69;
	loop(i, 1, 1e6 + 3)
		pot[i] = (podst * pot[i - 1]) % MOD;

	int t;
	cin >> t;
	while (t--) solve();
}