A,B=gets,gets.split
L=[]
R=[]
U=[]
D=[]
N=[]
C=[]
S=[]
O=[0]*81
z='A'
(0..324).map{|j|U<<j;D<<j;R<<(j+1)%325;L<<(j+324)%325;N<<j;C<<j;S<<0}
X=->s,j,c,cf,n{
  j<81 ? (z==A[j]?(0..8).map{|i|X[s-1-i,j+1,c+[i],cf+[1+j,1+81+27*i+j/9,1+81+27*i+9+j%9,1+81+27*i+18+j/3%3+j/27*3],n+[i+1]]}:X[s,j+1,c,cf,n+[0]]if s>=0)
       : (h=U.size;cf.uniq.sort.map{|l|N<<n;L<<(L[h]||h);R<<h;U<<U[l];D<<l;C<<l;S[l]+=1;L[R[-1]]=R[L[-1]]=U[D[-1]]=D[U[-1]]=L.size-1}if s==0)
}
Y=->c{L[R[c]]=L[c];R[L[c]]=R[c];i=D[c];(j=R[i];(U[D[j]]=U[j];D[U[j]]=D[j];S[C[j]]-=1;j=R[j])while j!=i;i=D[i])while i!=c}
Z=->c{i=U[c];(j=L[i];(S[C[j]]+=1;U[D[j]]=j;D[U[j]]=j;j=L[j])while j!=i;i=U[i])while i!=c;L[R[c]]=c;R[L[c]]=c}
B.map{|k|X[k.to_i,0,[],[],[]];z=z=='Z'?'a':z.next}
s=->k{
  c=R[0]
  c<1 ? ($><<(O[0,k].map{|s|N[s]}.transpose.map &:max)*"")
      : (g=S[b=c];g=S[b=c]if S[c]<g while 0<c=R[c];Y[b];r=D[b];(O[k]=r;j=R[r];(Y[C[j]];j=R[j])while j!=r;s[k+1];r=O[k];c=C[r];j=L[r];(Z[C[j]];j=L[j])while j!=r;r=D[r])while r!=b;Z[b])
}
s[0]
 
 

QSxCPWdldHMsZ2V0cy5zcGxpdApMPVtdClI9W10KVT1bXQpEPVtdCk49W10KQz1bXQpTPVtdCk89WzBdKjgxCno9J0EnCigwLi4zMjQpLm1hcHt8anxVPDxqO0Q8PGo7Ujw8KGorMSklMzI1O0w8PChqKzMyNCklMzI1O048PGo7Qzw8ajtTPDwwfQpYPS0+cyxqLGMsY2YsbnsKICBqPDgxID8gKHo9PUFbal0/KDAuLjgpLm1hcHt8aXxYW3MtMS1pLGorMSxjK1tpXSxjZitbMStqLDErODErMjcqaStqLzksMSs4MSsyNyppKzkraiU5LDErODErMjcqaSsxOCtqLzMlMytqLzI3KjNdLG4rW2krMV1dfTpYW3MsaisxLGMsY2YsbitbMF1daWYgcz49MCkKICAgICAgIDogKGg9VS5zaXplO2NmLnVuaXEuc29ydC5tYXB7fGx8Tjw8bjtMPDwoTFtoXXx8aCk7Ujw8aDtVPDxVW2xdO0Q8PGw7Qzw8bDtTW2xdKz0xO0xbUlstMV1dPVJbTFstMV1dPVVbRFstMV1dPURbVVstMV1dPUwuc2l6ZS0xfWlmIHM9PTApCn0KWT0tPmN7TFtSW2NdXT1MW2NdO1JbTFtjXV09UltjXTtpPURbY107KGo9UltpXTsoVVtEW2pdXT1VW2pdO0RbVVtqXV09RFtqXTtTW0Nbal1dLT0xO2o9UltqXSl3aGlsZSBqIT1pO2k9RFtpXSl3aGlsZSBpIT1jfQpaPS0+Y3tpPVVbY107KGo9TFtpXTsoU1tDW2pdXSs9MTtVW0Rbal1dPWo7RFtVW2pdXT1qO2o9TFtqXSl3aGlsZSBqIT1pO2k9VVtpXSl3aGlsZSBpIT1jO0xbUltjXV09YztSW0xbY11dPWN9CkIubWFwe3xrfFhbay50b19pLDAsW10sW10sW11dO3o9ej09J1onPydhJzp6Lm5leHR9CnM9LT5rewogIGM9UlswXQogIGM8MSA/ICgkPjw8KE9bMCxrXS5tYXB7fHN8TltzXX0udHJhbnNwb3NlLm1hcCAmOm1heCkqIiIpCiAgICAgIDogKGc9U1tiPWNdO2c9U1tiPWNdaWYgU1tjXTxnIHdoaWxlIDA8Yz1SW2NdO1lbYl07cj1EW2JdOyhPW2tdPXI7aj1SW3JdOyhZW0Nbal1dO2o9UltqXSl3aGlsZSBqIT1yO3NbaysxXTtyPU9ba107Yz1DW3JdO2o9TFtyXTsoWltDW2pdXTtqPUxbal0pd2hpbGUgaiE9cjtyPURbcl0pd2hpbGUgciE9YjtaW2JdKQp9CnNbMF0KCg==

QUFCQkJDREVGR0dISENDREVGR0dJSUNKS0tGTE1NSU5KS09GTFBQUU5KT09SU1BUUU5VVlZSU1RUUVdVVVhYU1laV1dhYVhYU1laV2JiYmNjCjMgMTUgMjIgNCAxNiAxNSAyNSAxNyA5IDggMjAgNiAxNCAxNyAxNyAxMyAyMCAxMiAyNyA2IDIwIDYgMTAgMTQgOCAxNiAxNSAxMyAxNwo=

AABBBCDEFGGHHCCDEFGGIICJKKFLMMINJKOFLPPQNJOORSPTQNUVVRSTTQWUUXXSYZWWaaXXSYZWbbbcc
3 15 22 4 16 15 25 17 9 8 20 6 14 17 17 13 20 12 27 6 20 6 10 14 8 16 15 13 17