cz_prob1 @ spoj

gistfile1.cpp

#include <iostream>
#include <vector>

using namespace std;

int sp2[] = {2,5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193,197,229,233,241,257,269,277,281,293,313,317,337,349,353,373,389,397,401,409,421,433,449,457,461,509,521,541,557,569,577,593,601,613,617,641,653,661,673,677,701,709,733,757,761,769,773,797,809,821,829,853,857,877,881,929,937,941,953,977,997,1009,1013,1021,1033,1049,1061,1069,1093,1097,1109,1117,1129,1153,1181,1193,1201,1213,1217,1229,1237,1249,1277,1289,1297,1301,1321,1361,1373,1381,1409,1429,1433,1453,1481,1489,1493,1549,1553,1597,1601,1609,1613,1621,1637,1657,1669,1693,1697,1709,1721,1733,1741,1753,1777,1789,1801,1861,1873,1877,1889,1901,1913,1933,1949,1973,1993,1997,2017,2029,2053,2069,2081,2089,2113,2129,2137,2141,2153,2161,2213,2221,2237,2269,2273,2281,2293,2297,2309,2333,2341,2357,2377,2381,2389,2393,2417,2437,2441,2473,2477,2521,2549,2557,2593,2609,2617,2621,2633,2657,2677,2689,2693,2713,2729,2741,2749,2753,2777,2789,2797,2801,2833,2837,2857,2861,2897,2909,2917,2953,2957,2969,3001,3037,3041,3049,3061,3089,3109,3121,3137,3169,3181,3209,3217,3221,3229,3253,3257,3301,3313,3329,3361,3373,3389,3413,3433,3449,3457,3461,3469,3517,3529,3533,3541,3557,3581,3593,3613,3617,3637,3673,3677,3697,3701,3709,3733,3761,3769,3793,3797,3821,3833,3853,3877,3881,3889,3917,3929,3989,4001,4013,4021,4049,4057,4073,4093,4129,4133,4153,4157,4177,4201,4217,4229,4241,4253,4261,4273,4289,4297,4337,4349,4357,4373,4397,4409,4421,4441,4457,4481,4493,4513,4517,4549,4561,4597,4621,4637,4649,4657,4673,4721,4729,4733,4789,4793,4801,4813,4817,4861,4877,4889,4909,4933,4937,4957,4969,4973,4993,5009,5021,5077,5081,5101,5113,5153,5189,5197,5209,5233,5237,5261,5273,5281,5297,5309,5333,5381,5393,5413,5417,5437,5441,5449,5477,5501,5521,5557,5569,5573,5581,5641,5653,5657,5669,5689,5693,5701,5717,5737,5741,5749,5801,5813,5821,5849,5857,5861,5869,5881,5897,5953,5981,6029,6037,6053,6073,6089,6101,6113,6121,6133,6173,6197,6217,6221,6229,6257,6269,6277,6301,6317,6329,6337,6353,6361,6373,6389,6397,6421,6449,6469,6473,6481,6521,6529,6553,6569,6577,6581,6637,6653,6661,6673,6689,6701,6709,6733,6737,6761,6781,6793,6829,6833,6841,6857,6869,6917,6949,6961,6977,6997,7001,7013,7057,7069,7109,7121,7129,7177,7193,7213,7229,7237,7253,7297,7309,7321,7333,7349,7369,7393,7417,7433,7457,7477,7481,7489,7517,7529,7537,7541,7549,7561,7573,7577,7589,7621,7649,7669,7673,7681,7717,7741,7753,7757,7789,7793,7817,7829,7841,7853,7873,7877,7901,7933,7937,7949,7993};

int prime(int n)
{
	if ((n & 1) == 0) return n == 2;

	for (int i=3; i<n; i += 2) {
		if ((n % i) == 0) return 0;
	}

	return 1;
}

int sqsum(int n)
{
	for (int i=0; i<=n; i++) {
		for (int j=i; j<=n; j++) {
			if ((i*i + j*j) == n) {
				cout << i << " " << j << " " <<  "," << n << endl;
				return 1;
			}
		}
	}
	return 0;
}

void calcsp2()
{
	int n = 2;

	for (int n=2; n < 100; n++) {
		if (!prime(n)) continue;
		if (!sqsum(n)) continue;
		//sp2.push_back(n);
	}
}

long long m[8000][5];

long long p(int a, int b)
{
	if (b == 1)
		return 1;
	if (a == 1)
		return 1;
	if (a == 0)
		return 1;
	if (a < 0)
		return 0;

	if (m[a][b] != -1) return m[a][b];

	long long sum = 0;
	for (int i=1; i<=b; i++) {
		sum += p(a-i, i);
	}

	m[a][b] = sum;

	return sum;
}

int main()
{
	for (int i=0; i<8000; i++) {
		for (int j=0; j<5; j++) {
			m[i][j] = -1;
		}
	}

	int t;
	cin >> t;

	while (t--) {
		int n, k;
		cin >> n >> k;

		int a = sp2[n-1];

		cout << p(a, k) << endl;
	}

	return 0;
}