#define modulus 100
#define lobits(k) ((1u<<(k) ) -1) 
#define gosper(b) {register int x= b,y; \
x= b&-b,y= b+x; \
b= y+(((y^b) /x) >>2) ;} \

/*1:*/
#line 38 "perfect-partition-square.w"

#include <stdio.h> 
#include <stdlib.h> 
int parts[14]= {
0x6100000,
0x5200000,
0x5110000,
0x4300000,
0x4210000,
0x4111000,
0x3310000,
0x3220000,
0x3211000,
0x3111100,
0x2221000,
0x2211100,
0x2111110,
0x1111111};
int rparts[8][8],cparts[8][8];
char a[8][8];
unsigned long long count;
/*3:*/
#line 81 "perfect-partition-square.w"

void verify(int l);
void place(int l){
register int b,i,j,k,m,p,max,abits,bbits,thisrow,thiscol= -1;
if(l==0)/*8:*/
#line 197 "perfect-partition-square.w"

{
count++;
if((count%
modulus)==0){
printf("%lld: ",
count);
for(i= 0;i<7;i++){
for(j= 0;j<7;j++)printf("%d",
a[i][j]);
printf("%c",
i<6?' ':'\n');
}
}
return;
}

/*:8*/
#line 85 "perfect-partition-square.w"
;
for(max= i= 0;i<7;i++)
if(rparts[l][i]> max)max= rparts[l][i],thisrow= i;
for(j= 0;j<7;j++)if(cparts[l][j]> max)max= cparts[l][j],thiscol= j;
if(thiscol>=0)/*5:*/
#line 121 "perfect-partition-square.w"

{
p= max>>24;
for(m= 0;max;m+= max&0xf,max>>= 4);
for(abits= lobits(p);abits<1<<m;){
for(b= 1,i= 0;i<7;i++)if(!a[i][thiscol]){
if(abits&b)a[i][thiscol]= l;
b<<= 1;
}
for(bbits= lobits(7-p);bbits<1<<(7*l-m);){
for(b= 1,j= 0;j<7;j++)if(j!=thiscol){
for(i= 0;i<7;i++)if(!a[i][j]){
if(bbits&b)a[i][j]= l;
b<<= 1;
}
}
verify(l);
for(j= 0;j<7;j++)if(j!=thiscol){
for(i= 0;i<7;i++)if(a[i][j]==l)a[i][j]= 0;
}
gosper(bbits);
}
for(i= 0;i<7;i++)
if(a[i][thiscol]==l)a[i][thiscol]= 0;
gosper(abits);
}
}

/*:5*/
#line 89 "perfect-partition-square.w"

else/*4:*/
#line 93 "perfect-partition-square.w"

{
p= max>>24;
for(m= 0;max;m+= max&0xf,max>>= 4);
for(abits= lobits(p);abits<1<<m;){
for(b= 1,j= 0;j<7;j++)if(!a[thisrow][j]){
if(abits&b)a[thisrow][j]= l;
b<<= 1;
}
for(bbits= lobits(7-p);bbits<1<<(7*l-m);){
for(b= 1,i= 0;i<7;i++)if(i!=thisrow){
for(j= 0;j<7;j++)if(!a[i][j]){
if(bbits&b)a[i][j]= l;
b<<= 1;
}
}
verify(l);
for(i= 0;i<7;i++)if(i!=thisrow){
for(j= 0;j<7;j++)if(a[i][j]==l)a[i][j]= 0;
}
gosper(bbits);
}
for(j= 0;j<7;j++)
if(a[thisrow][j]==l)a[thisrow][j]= 0;
gosper(abits);
}
}

/*:4*/
#line 90 "perfect-partition-square.w"
;
}

/*:3*//*6:*/
#line 149 "perfect-partition-square.w"

void verify(int l){
register int i,j,k,m,q;
for(i= 0;i<7;i++){
for(j= k= 0;j<7;j++)if(a[i][j]==l)k++;
m= rparts[l][i];
if(k> 0){
for(;m;m>>= 4)if((m&0xf)==k)goto rowgotk;
return;
}else{
if(m&(lobits(4*(8-l))))return;
}
rowgotk:continue;
}
for(j= 0;j<7;j++){
for(i= k= 0;i<7;i++)if(a[i][j]==l)k++;
m= cparts[l][j];
if(k> 0){
for(;m;m>>= 4)if((m&0xf)==k)goto colgotk;
return;
}else{
if(m&(lobits(4*(8-l))))return;
}
colgotk:continue;
}
/*7:*/
#line 180 "perfect-partition-square.w"

for(i= 0;i<7;i++){
for(j= k= 0;j<7;j++)if(a[i][j]==l)k++;
if(k> 0){
for(m= rparts[l][i],q= 24;((m>>q)&0xf)!=k;q-= 4);
rparts[l-1][i]= (m&-(1<<(q+4)))+((m&lobits(q))<<4);
}else rparts[l-1][i]= rparts[l][i];
}
for(j= 0;j<7;j++){
for(i= k= 0;i<7;i++)if(a[i][j]==l)k++;
if(k> 0){
for(m= cparts[l][j],q= 24;((m>>q)&0xf)!=k;q-= 4);
cparts[l-1][j]= (m&-(1<<(q+4)))+((m&lobits(q))<<4);
}else cparts[l-1][j]= cparts[l][j];
}
place(l-1);

/*:7*/
#line 174 "perfect-partition-square.w"
;
}

/*:6*/
#line 59 "perfect-partition-square.w"
;
int main(void){
register int b,i,j,k,bits;
cparts[7][6]= parts[13];
for(bits= lobits(6);bits<1<<13;){
/*2:*/
#line 71 "perfect-partition-square.w"

for(i= j= k= 0,b= 1<<12;b;b>>= 1,k++){
if(bits&b)cparts[7][j++]= parts[k];
else rparts[7][i++]= parts[k];
}
place(7);

/*:2*/
#line 64 "perfect-partition-square.w"
;
fprintf(stderr,"finished subproblem %x; so far %lld solutions.\n",
bits,count);
gosper(bits);
}
}

/*:1*/