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

Bajtek 很伤心，因为并不是所有的单词都是回文。一位朋友告诉他，在任何单词中都可以找到一个子串（即连续的字母序列）是回文。Bajtek 起初很高兴，但后来意识到只需要取第一个字母（因为单字母单词总是回文），他认为这是一种作弊。

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

给定数字 $n$ 和 $k$，请输出一个长度为 $n$、由字母 P 和 A 组成的单词，其中最长的回文子串长度恰好为 $k$（如果无法做到，请说明）。

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

注意：由于本题的特殊性质，禁止与其他选手分享测试数据。

输入格式

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

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

所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

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

样例

输入格式 1

3
2 1
4 3
10 1

输出格式 1

PA
AAPA
NIE

说明

在第一个测试用例中，示例答案中长度为 1 的回文既有子串 P 也有子串 A。单词 AP 也是正确的答案。

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

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