SPOJ Problem Set (classical) 1391. Summing to a Square Prime Problem code: CZ_PROB1

S_P2 = {p | p = x₁² + x₂² for some x₁, x₂ belonging to Z} is the set of all primes that can be represented as the sum of any two squares. The function S_P2(n) gives the n^th prime number from the set S_P2. Now, given two integers n (0P2(n), k) where p(a, b) gives the number of unordered ways to sum to the given total ‘a’ with ‘b’ as its largest part. For example: p(5, 2) = 3 {2+2+1, 2+1+1+1, and 1+1+1+1+1}. Here 5 is the total with 2 as the largest part.

Input

The first line gives the number of test cases T followed by T lines of integer pairs, n and k.
Scope:
0 < T < 501
0 < n < 501
1 < S_P2(n) < 7994
0 < k < 4

Output

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

---

Added by:	Rahul
Date:	2007-03-10
Time limit:	2s
Source limit:	3000B
Languages:	All except: CLOJ ERL F# JS PERL 6 TECS
Resource:	Sam Collins