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
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
using namespace std;

const unsigned long long BASE=131;

unsigned long long pows[1000005];

int n,k;

string res;

unsigned long long hfwd[1000005];
unsigned long long hrev[1000005];

bool found;

bool pal(int l, int r)
{
    if(l<0)
    {
        return false;
    }

    int len=r-l+1;

    unsigned long long fwd=hfwd[r+1]-hfwd[l]*pows[len];
    unsigned long long rev=hrev[r+1]-hrev[l];

    return fwd*pows[l]==rev;
}

void dfs(int idx, bool has)
{
    if(found)
    {
        return;
    }

    if(idx==n)
    {
        if(has)
        {
            found=true;
        }

        return;
    }

    for(char c : {'P','A'})
    {
        res[idx]=c;

        unsigned long long val=(c=='P' ? 1 : 2);

        hfwd[idx+1]=hfwd[idx]*BASE+val;
        hrev[idx+1]=hrev[idx]+val*pows[idx];

        if(pal(idx-k,idx) || pal(idx-k-1,idx))
        {
            continue;
        }

        bool current=has || pal(idx-k+1,idx);

        dfs(idx+1,current);

        if(found)
        {
            return;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    pows[0]=1;

    for(int i=1; i<=1000000; i++)
    {
        pows[i]=pows[i-1]*BASE;
    }

    int t;
    cin>>t;

    while(t--)
    {
        cin>>n>>k;

        res.assign(n,' ');

        found=false;

        hfwd[0]=0;
        hrev[0]=0;

        dfs(0,false);

        if(found)
        {
            cout<<res<<endl;
        }
        else
        {
            cout<<"NIE"<<endl;
        }
    }

    return 0;
}