CZ_PROB1 - Summing to a Square Prime


SP2={pp:prime(x1,x2Z,p=x21+x22)} is the set of all primes that can be represented as the sum of two squares. The function SP2(n) gives the nth prime number from the set SP2. Now, given two integers n (0<n<501) and k (0<k<4), find p(SP2(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.

Input

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

Constraints

  • 0<T<501
  • 0<n<501
  • 1<SP2(n)<7994
  • 0<k<4

Output

The p(SP2(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

hide comments
Mitch Schwartz: 2011-09-06 23:36:18

Suggest changing "with ‘b’ as its largest part" to "with ‘b’ as its largest possible part" and similarly for "with 2 as the largest part".

Last edit: 2011-09-07 00:56:41

Added by:Rahul
Date:2007-03-10
Time limit:1s
Source limit:3000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Sam Collins