#include <stdio.h>

int inuse[16];
int results[16+15+14];

FILE *fout;

int check(int number)
{
	if (number > 0 && number < 17 && !inuse[number-1])
	{
		return inuse[number-1]=1;
	}
	return 0;
}

void free(int number)
{
	inuse[number-1]=0;
}

void out(int t, int* p)
{
	int i;
	fprintf(fout, "\n%d",t);
	for(i=0; i< 16; i++) fprintf(fout, " %d",*p++);
}

void scan() 
{
	int p[16];
	int t,i;
	for (p[0]=0; p[0]++<16;) if (check(p[0]))
	{
		for (p[1]=0; p[1]++<16;) if (check(p[1]))
		{
			for (p[2]=0; p[2]++<16;) if (check(p[2]))
			{
				t = p[0]+p[1]+p[2]; // top horiz: 0,1,2
				for (p[7]=0; p[7]++<16;) if (check(p[7]))
				{
					if (check(p[11] = t-p[7]-p[2])) // right vert: 2,7,11
					{
						for(p[9]=0; p[9]++<16;) if (check(p[9]))
						{
							for (p[10]=0; p[10]++<16;) if (check(p[10]))
							{
								if (check(p[12] = t-p[9]-p[10]-p[11])) // right horiz: 9,10,11,12
								{
									for(p[6]=0; p[6]++<16;) if (check(p[6]))
									{
										if (check(p[15] = t-p[0]-p[6]-p[9])) // middle vert: 0,6,9,15
										{
											for(p[13]=0; p[13]++<16;) if (check(p[13]))
											{
												if (check(p[14] = t-p[13]-p[15])) // bottom horiz:  13,14,15
												{
													for(p[4]=0; p[4]++<16;) if (check(p[4]))
													{
														if (check(p[8] = t-p[4]-p[13])) // left vert: 4,8,13
														{
															for(p[3]=0; p[3]++<16;) if (check(p[3]))
															{
																if (check(p[5] = t-p[3]-p[4]-p[6])) // left horiz: 3,4,5,6
																{
																	++results[t];
																	//out(t,p);
																	free(p[5]);
																}
																free(p[3]);
															}
															free(p[8]);
														}
														free(p[4]);
													}
													free(p[14]);
												}
												free(p[13]);
											}
											free(p[15]);
										}
										free(p[6]);
									}
									free(p[12]);
								}
								free(p[10]);
							}
							free(p[9]);
						}
						free(p[11]);
					}
					free(p[7]);
				}    
				free(p[2]);
			} 
			free(p[1]);
		}
		free(p[0]);
	}
	for(i=0;i<15+16+14;i++)
	{
		if(results[i]) printf("%d %d\n", i, results[i]);
	}
}


void main()
{
	//fout = fopen("c:\\temp\\puzzle29.txt", "w");
	scan();
	//fclose(fout);
}