[AdditionalFile5688.zip](file://AdditionalFile5688.zip?type=additional_file)

#5688. 「PA 2026」Palindromy

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2026 Runda 5 Palindromy

Bajtek 非常喜欢回文串。回文串是指从左往右读和从右往左读都一样的字符串。因此，KAJAK、ANNA 或 0 都是回文串，而 BABA、OFF 或 AS 则不是。

Bajtka 很难过，因为并不是所有的单词都是回文串。朋友告诉他，在任何单词中都可以找到一个子串（即连续的字母序列）是回文串。Bajtka 听后很高兴，但随后意识到，只要取第一个字母（因为单个字母总是回文串）就可以了，他认为这属于作弊。

因此，他决定尝试写一个单词（长度不限），使得其中最长的回文子串长度恰好为 $k$。目前 Bajtka 只会写字母 P 和 A，所以他的单词必须由这两个字母组成。

给定数字 $n$ 和 $k$，请输出一个长度为 $n$、由字符 P 和 A 组成的字符串，使得其中最长的回文子串长度恰好为 $k$（或者指出不存在这样的字符串）。

你需要为 $t$ 个独立的测试用例解决此问题。

输入格式

第一行输入包含一个整数 $t$ $(1 \leq t \leq 10000)$，表示测试用例的数量。

每个测试用例只有一行，包含两个整数 $n$ 和 $k$ $(1 \leq k \leq n \leq 10^{6})$，分别表示预期的单词长度和最长回文子串的长度。

所有测试用例中 $n$ 的总和不超过 $10^{6}$。

输出格式

输出 $t$ 行。第 $i$ 行应包含一个满足第 $i$ 个测试用例条件的字符串。如果不存在这样的字符串，则输出 NIE。如果存在多个这样的字符串，输出其中任意一个即可。

样例

输入

3
2 1
4 3
10 1

输出

PA
AAPA
NIE

在第一个测试用例中，样例输出中答案中长度为 $1$ 的回文子串既可以是 P 也可以是 A。输出 AP 也是正确的答案。

在第二个测试用例中，唯一长度为 $3$ 的回文子串是 APA。输出 PAPA 在本题中也是正确的（其中两个长度为 $3$ 的子串都是回文串），但不能输出 AAAA（因为其中最长的回文串长度为 $4$），也不能输出 PPAA（其中最长的回文串长度为 $2$）。

在第三个测试用例中，不存在长度如此之长且没有长度超过 $1$ 的回文串的单词。