SP1391 CZ_PROB1 - Summing to a Square Prime

MathJax.Hub.Config({ tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], skipTags: ["script","noscript","style","textarea","code"] } }); $S\_{P2} = \\{p \\mid p: \\mathrm{prime} \\wedge (\\exists x\_1, x\_2 \\in \\mathbb{Z}, p = x\_1^2 + x\_2^2) \\}$ is the set of all primes that can be represented as the sum of two squares. The function $S\_{P2}(n)$ gives the $n$ $ ^{th} $ prime number from the set $S\_{P2}$. Now, given two integers $n$ ($0 < n < 501$) and $k$ ($0 < k < 4$), find $p(S\_{P2}(n), k)$ where $p(a, b)$ gives the number of unordered ways to sum to the given total ‘$a$’ with ‘$b$’ as its largest possible part. For example: $p(5, 2) = 3$ (i.e. $2+2+1$, $2+1+1+1$, and $1+1+1+1+1$). Here $5$ is the total with $2$ as its largest possible part.

The first line gives the number of test cases $T$ followed by $T$ lines of integer pairs, $n$ and $k$.

The $p(S\_{P2}(n), k)$ for each $n$ and $k$. Append a newline character to every test cases’ answer. ### Example ``` Input: 3 2 2 3 2 5 3 Output: 3 7 85 ```