Little Bajtek really likes palindromes. A palindrome is a word that reads the same from left to right as it does from right to left. Thus, words like KAJAK, ANNA, or O are palindromes, while words like BABA, OFF, or AS are not.

Bajtek is saddened that not all words are palindromes. A friend told him that in every word, one can find a substring—a contiguous sequence of letters—that is a palindrome. Bajtek was very happy at first, but then he realized that one could simply take the first letter (since a single-letter word is always a palindrome), and he considered that cheating.

He decided to try to write a word (as long as he wants) in which the longest substring that is a palindrome has exactly the length he desires. For now, Bajtek only knows how to write the letters P and A, so the word he writes must consist of these letters.

Given the numbers $n$ and $k$, output a word of length $n$ consisting of the letters P and A, in which the longest substring that is a palindrome has a length of exactly $k$ (or state that it is impossible).

You must solve this problem for $t$ independent test cases.

Note: Due to the specific nature of this task, sharing test cases with other contestants is prohibited.

Input

The first line of input contains a number $t$ ($1 \le t \le 10\,000$), representing the number of test cases.

Each test case consists of a single line containing two integers $n$ and $k$ ($1 \le k \le n \le 10^6$), representing the expected length of the word and the length of the longest substring that is a palindrome.

The sum of $n$ over all test cases will not exceed $10^6$.

Output

The output should contain $t$ lines. The $i$-th line should contain a single word satisfying the conditions given in the $i$-th test case. If no such word exists, the $i$-th line should contain the word NIE. If more than one such word exists, output any one of them.

Examples

Input 1

3
2 1
4 3
10 1

Output 1

PA
AAPA
NIE

Note

In the first test case, a palindrome of length 1 in the sample answer is both the substring P and the substring A. The word AP would also be a correct answer.

In the second test case, the only palindromic substring of length 3 is APA. A correct answer for this test would also be the word PAPA (in which both substrings of length 3 are palindromes), but not the word AAAA (because the longest palindrome in it has length 4), nor PPAA (in which the longest palindrome has length 2).

In the third test case, there is no such long word without a palindrome longer than 1.