#include <stdio.h>
#include <math.h>


#define	VD	void
#define	U1	unsigned char
#define	U4	unsigned int

#define	APL_FALSE	(0)
#define	APL_TRUE	(1)

#define MAX_INPUT_N				(32768)		/* 2^15*/
#define NUM_PRIME_NUMBER_ARR	(10000)		/* 2^15??\???????´???°?????°??????????´???§????????§??????????¢???? */
#define PRIME_NUM_5				(5)			/* ?´???°??¢?´¢????§??????° */

static VD vd_s_createPrimeNumArr(U4** u4_ap_rtnArr);
static U4 u4_s_countPairs(U4 u4_a_inputN, U4* u4_ap_PrimeNumArr);

U4 main()
{
	U4 u4_tp_PrimeNumArr[NUM_PRIME_NUMBER_ARR];
	U4 u4_t_inputN;
	U4 u4_t_numPairs;
	u4_t_inputN = (U4)0;
	u4_t_numPairs = (U4)0;
	/* ??\????????¨????¨????????????????????????§??????????´???°????????????????????£????????? */
	/* TODO:?´???°??????????????????????????????????????????????????§?????? */
	vd_s_createPrimeNumArr(&u4_tp_PrimeNumArr[0]);

	while (1)
	{
		scanf("%d", &u4_t_inputN);
		if (u4_t_inputN == 0)
		{
			break;
		}

		u4_t_numPairs = u4_s_countPairs(u4_t_inputN, u4_tp_PrimeNumArr);
		printf("%d\n", u4_t_numPairs);
	}
	return((U4)0);
}

VD vd_s_createPrimeNumArr(U4 ** u4_ap_rtnArr)
{
	U4 u4_t_i;
	U4 u4_t_j;
	U4 u4_t_primeIndex;
	U4 u4_t_searchCap;
	U1 u1_t_isPrime;
	u4_t_i = (U4)0;
	u4_t_j = (U4)0;
	u4_t_primeIndex = (U4)0;

	u1_t_isPrime = (U1)APL_FALSE;

	/* 2, 3????´???° */
	u4_ap_rtnArr[0] = (U4)2;
	u4_ap_rtnArr[1] = (U4)3;
	u4_t_primeIndex = (U4)2;

	/* 3????¬?????\???°????????¢?´¢????§? */
	/* ??¶??°????´???°??§??????????????¢?´¢?????? */
	for (u4_t_i = (U4)5; u4_t_i <= (U4)MAX_INPUT_N; u4_t_i += (U4)2)
	{
		u1_t_isPrime = (U1)APL_TRUE;
		u4_t_searchCap = (U4)sqrt(u4_t_i) + (U4)1;	/* ?´???°??§????????????????????\????????°????´???°??¨????????????????????¢?´¢??????????????§??§OK */

		/* ????????°??§???????????????????´???°??§????????? */
		u4_t_j = (U4)3;		/* ??\????????????????\???°???2??§??????????????????????¢?????????????????????§3????????????*/
		while ((u4_t_j <= u4_t_searchCap) &&
			   (u1_t_isPrime != (U1)APL_FALSE))
		{
			/* ????????°??§???????????????????´???°??§????????? */
			if ((u4_t_i % u4_t_j) == 0)
			{
				u1_t_isPrime = (U4)APL_FALSE;
			}
			u4_t_j++;
		}

		/* ?´???°?????? */
		if (u1_t_isPrime == (U1)APL_TRUE)
		{
			u4_ap_rtnArr[u4_t_primeIndex] = u4_t_i;
			u4_t_primeIndex++;
		}

	}
	return;
}

U4 u4_s_countPairs(U4 u4_a_inputN, U4 * u4_ap_PrimeNumArr)
{
	U4 u4_t_prime1;
	U4 u4_t_prime2;
	U4 u4_t_i;
	U4 u4_t_primeIndex;
	U4 u4_t_cntPair;
	U4 u4_t_maxSearchNum;
	
	/* ?????????CS??????((????????????????????¢) */
	u4_t_prime1 = (U4)0;
	u4_t_prime2 = (U4)0;
	u4_t_i = (U4)0;
	u4_t_cntPair = (U4)0;
	u4_t_primeIndex = (U4)0;
	u4_t_maxSearchNum = (U4)0;

	/* ?????????????´???°p?????????????????\???N-?´???°p????´???°??§??????????¢???? */
	u4_t_maxSearchNum = (U4)ceil((double)u4_a_inputN / 2.0);		/* ???????????????????????????????????????????????????????????????????????\??????????????°?????????????????§??¢?´¢ */
	for (u4_t_i = (U4)0; u4_ap_PrimeNumArr[u4_t_i] <= u4_t_maxSearchNum; u4_t_i++)
	{
		/* ?´???°???????????????N-p????????????????????¢?´¢ */
		u4_t_prime2 = u4_a_inputN - u4_ap_PrimeNumArr[u4_t_i];
		u4_t_primeIndex = (U4)0;
		while((u4_t_primeIndex < (U4)NUM_PRIME_NUMBER_ARR) &&
			  (u4_ap_PrimeNumArr[u4_t_primeIndex] <= u4_a_inputN)) 
		{
			/* N-p????´???° */
			if (u4_ap_PrimeNumArr[u4_t_primeIndex] == u4_t_prime2)
			{
				u4_t_cntPair++;
			}
			u4_t_primeIndex++;
		}
	}

	return(u4_t_cntPair);
}

Measured memory_bytes: 636