#include <stdio.h>
#include <iostream>
using namespace std;
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))
#define MAX(X,Y) ((X) > (Y) ? (X) : (Y))
int numPrime;
int numCase[1001];
int primeList[1001];
void init(void)
{
numPrime = 1;
primeList[0] = 2;
for (int i = 3; i <= 999; i += 2) {
for (int j = 0; j < numPrime; j++) {
if (i % primeList[j] == 0) {
break;
}
else if (i <= primeList[j] * primeList[j]) {
primeList[numPrime++] = i;
break;
}
}
}
for (int i = 0; i < numPrime; i++) {
for (int j = i; j < numPrime; j++) {
for (int k = j; k < numPrime; k++) {
int sum = primeList[i] + primeList[j] + primeList[k];
if (sum <= 1000) {
numCase[sum]++;
}
}
}
}
}
int main(int argc, char *argv[])
{
freopen("input.txt", "r", stdin);
int TC;
scanf("%d", &TC);
init();
int TCI = 0;
while (TC-- > 0) {
TCI++;
int q;
scanf("%d", &q);
printf("#%d %d\n", TCI, numCase[q]);
}
return 0;
}
댓글