Problem Description

Little Bajtek really likes palindromes. A palindrome is a word that reads exactly the same from left to right as from right to left. Therefore, KAJAK, ANNA, and $0$ are palindromes, while BABA, OFF, and AS are not.

Bajtek is sad because not all words are palindromes. His friend told him that in any word, you can find a substring, that is, a consecutive sequence of letters, which is a palindrome. Bajtek was very happy, but then he realized that taking just the first letter (since any one-letter word is always a palindrome) feels like cheating.

So he decided to try to write a word (as long as he wants) such that the longest palindromic substring in it has exactly the length he wants. Bajtek currently can only write the letters P and A, so the word must consist only of these two letters.

Given numbers $n$ and $k$, output a word of length $n$ consisting of the letters P and A such that the length of its longest palindromic substring is exactly $k$ (if it is impossible, output that there is no solution).

You need to solve $t$ independent test cases.

Input Format

The first line of input contains an integer $t$ ($1 \le t \le 10000$), the number of test cases.

The only line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 10^6$), meaning the desired word length and the length of the longest palindromic substring. The sum of $n$ over all test cases does not exceed $10^6$.

Output Format

The output should contain $t$ lines. The $i$-th line should contain one word that satisfies the conditions for the $i$-th test case. If no such word exists, the $i$-th line should output NIE (meaning "no"). If multiple valid words exist, output any one of them.

3
2 1
4 3
10 1

PA
AAPA
NIE

Hint

Sample Explanation

In the first test case, in the sample answer, palindromic substrings of length $1$ include the substring P and the substring A. The word AP is also a correct answer.

In the second test case, the only palindromic substring of length $3$ is APA. In this test case, the word PAPA is also a correct answer (both substrings of length $3$ are palindromes), but the word AAAA is not a correct answer (because its longest palindrome has length $4$), and the word PPAA is also not a correct answer (its longest palindrome has length $2$).

In the third test case, there is no such long word whose longest palindromic substring length is at most $1$.

Translated by ChatGPT 5